An algorithm for packing connectors

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)

    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 languageEnglish
    Pages (from-to)397-404
    Number of pages8
    JournalJournal of Combinatorial Theory, Series B
    Volume74
    Issue number2
    DOIs
    Publication statusPublished - 1998

    Fingerprint Dive into the research topics of 'An algorithm for packing connectors'. Together they form a unique fingerprint.

    Cite this