Splitting formulas for Tutte polynomials
type: Item
instance of: scholarly article
title: Splitting formulas for Tutte polynomials
zbMATH Open document ID: 0878.05021
author: Artur Andrzejak
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-08-12T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 1042505
zbMATH Keywords: Tutte polynomial
zbMATH Keywords: matroid
reviewed by: Volkmar Welker
MaRDI profile type: Publication
OpenAlex ID: W2015199322
cites work: A Combinatorial Model for Series-Parallel Networks
cites work: Q4012032
cites work: On the computational complexity of the Jones and Tutte polynomials
cites work: Polynomial Invariants of Graphs
cites work: Q3135082
cites work: Tutte polynomials computable in polynomial time
cites work: Decomposition of regular matroids
cites work: Q3140234
DOI: 10.1006/JCTB.1997.1767
Recommended article: Q3447288
Recommended article: Q4845264
Recommended article: Series and parallel reductions for the Tutte polynomial
Recommended article: The complexity of computing the Tutte polynomial on transversal matroids
Recommended article: Computational resources
Recommended article: The Tutte polynomial of a morphism of matroids. IV: Computational complexity
Recommended article: Tutte polynomials of generalized parallel connections
Recommended article: The Tutte Polynomial for Matroids of Bounded Branch-Width
Recommended article: The complexities of the coefficients of the Tutte polynomial
Recommended article: The Tutte polynomial of some matroids
description: scientific article; zbMATH DE number 1042505