An algorithm for packing connectors

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    2 Citaten (Scopus)


    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.
    Originele taal-2Engels
    Pagina's (van-tot)397-404
    Aantal pagina's8
    TijdschriftJournal of Combinatorial Theory, Series B
    Nummer van het tijdschrift2
    StatusGepubliceerd - 1998


    Duik in de onderzoeksthema's van 'An algorithm for packing connectors'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit