Abstract
Given an undirected graphG=(V, E) and a partition {S, T} ofV, anS-Tconnectoris a set of edgesF¿Esuch that every component of the subgraph (V, F) intersects bothSandT. If eitherSorTis a singleton, then anS-Tconnector is a spanning subgraph ofG. On the other hand, ifGis bipartite with colour classesSandT, then anS-Tconnector is an edge cover ofG(a set of edges covering all vertices). AnS-Tconnector is a common spanning set of two graphic matroids onE. 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 anO(t(n, m)+nm) time algorithm for finding a maximum number ofS-Tconnectors, wheret(n, m) denotes the complexity of finding a maximum number of edge disjoint spanning trees in a graph onnvertices andmedges. Since the best known bound fort(n, m) isO(nm log(m/n)), this bound for packingS-Tconnectors is as good as the current bound for packing spanning trees.
| Original language | English |
|---|---|
| Pages (from-to) | 397-404 |
| Number of pages | 8 |
| Journal | Journal of Combinatorial Theory, Series B |
| Volume | 74 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 1998 |