An Algorithm for Packing Connectors

✍ Scribed by J. Keijsper

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 256 KB
• Volume: 74
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1998.1863

✦ Synopsis

Given an undirected graph G=(V, E) and a partition [S, T] of V, an S&T connector is a set of edges F E such that every component of the subgraph (V, F) intersects both S and T. If either S or T is a singleton, then an S&T connector is a spanning subgraph of G. On the other hand, if G is bipartite with colour classes S and T, then an S&T connector is an edge cover of G (a set of edges covering all vertices). An S&T connector is a common spanning set of two graphic matroids on E. We prove a theorem on packing common spanning sets of certain matroids, generalizing a result of Davies and McDiarmid on strongly base orderable matroids. As a corollary, we obtain an O({(n, m)+nm) time algorithm for finding a maximum number of S&T connectors, where {(n, m) denotes the complexity of finding a maximum number of edge disjoint spanning trees in a graph on n vertices and m edges. Since the best known bound for {(n, m) is O(nm log(mÂn)), this bound for packing S&T connectors is as good as the current bound for packing spanning trees.