TY - JOUR
T1 - Matroid Steiner problems, the Tutte polynomial and network reliability
AU - Colbourn, Charles J.
AU - Pulleyblank, William R.
N1 - Funding Information:
* On leave at the Institut fur C)konometrie und Operations Research, Bonn, FRG. Supported by the joint project “Combinatorial Optimization” of the Natural Science and Engineering Research Council, Canada and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).
Funding Information:
Jason Brown pointed out how to shell the broken circuit complex using the Tutte polynomial, which suggested this line of research. Thanks also to Aniket Majumdar for some useful suggestions. Research of the authors is supported by NSERC Canada under Grants A0579 and A5249.
PY - 1989/8
Y1 - 1989/8
N2 - A matroid Steiner problem is obtained by selecting a suitable subfamily C of the cocircuits, and then defining a Steiner "tree" to be a minimal set having nonempty intersection with all members of C. The family of all sets whose complements contain Steiner trees forms an independence system which we call the Steiner complex. We show that this Steiner complex can be partitioned into as many intervals as there are bases in the underlying matroid. As a special case, we obtain explicit partitions of the independent sets of any matroid. It also shows that both F-complexes associated with network reliability problems and the family of bipartite subgraphs of a graph can be partitioned into as many intervals as there are spanning trees. We also describe a generalization of the Tutte polynomial for matroids to an extended Tutte polynomial for Steiner complexes. This provides an alternative method for evaluating the independence or reliability polynomial. We also discuss applications to network reliability.
AB - A matroid Steiner problem is obtained by selecting a suitable subfamily C of the cocircuits, and then defining a Steiner "tree" to be a minimal set having nonempty intersection with all members of C. The family of all sets whose complements contain Steiner trees forms an independence system which we call the Steiner complex. We show that this Steiner complex can be partitioned into as many intervals as there are bases in the underlying matroid. As a special case, we obtain explicit partitions of the independent sets of any matroid. It also shows that both F-complexes associated with network reliability problems and the family of bipartite subgraphs of a graph can be partitioned into as many intervals as there are spanning trees. We also describe a generalization of the Tutte polynomial for matroids to an extended Tutte polynomial for Steiner complexes. This provides an alternative method for evaluating the independence or reliability polynomial. We also discuss applications to network reliability.
UR - http://www.scopus.com/inward/record.url?scp=38249005915&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38249005915&partnerID=8YFLogxK
U2 - 10.1016/0095-8956(89)90062-2
DO - 10.1016/0095-8956(89)90062-2
M3 - Article
AN - SCOPUS:38249005915
SN - 0095-8956
VL - 47
SP - 20
EP - 31
JO - Journal of Combinatorial Theory, Series B
JF - Journal of Combinatorial Theory, Series B
IS - 1
ER -