
The Tutte polynomial is a central invariant of a matroid. In particular, many numerical invariants of a matroid can be calculated by evaluating or calculating coefficients of the Tutte polynomial. Moreover, for certain cases there is a close connection between the Tutte polynomial and the Jones and Kauffman polynomial of a link. Thus there is interest in effective algorithms calculating the Tutte polynomial. Unfortunately, it is know that in general computing the Tutte polynomial is \(\#P\)-hard. Nevertheless, there are classes of matroids that admit polynomial time algorithms. The paper under under review provides new instances of matroids for which this is possible. It shows that polynomial time algorithms exist for the class of generalized parallel connections across a \(3\)-point line and for \(3\)-sums of matroids. The concept of generalized parallel connections across a \(3\)-point line is introduced in the paper and extends the usual definition of parallel connection. Other instances of polynomial time algorithms for the Tutte polynomial can be found in the work of \textit{J. G. Oxley} and \textit{D. J. A. Welsh} [Discrete Math. 109, No. 1-3, 185-192 (1992; Zbl 0780.05011)].
Tutte polynomial, Computational Theory and Mathematics, matroid, Discrete Mathematics and Combinatorics, 000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik, Combinatorial aspects of matroids and geometric lattices, Theoretical Computer Science
Tutte polynomial, Computational Theory and Mathematics, matroid, Discrete Mathematics and Combinatorics, 000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik, Combinatorial aspects of matroids and geometric lattices, Theoretical Computer Science
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 13 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
