An approximate max-Steiner-tree-packing min-Steiner-cut theorem (Q925137)

From MaRDI portal
scientific article
Language Label Description Also known as
English
An approximate max-Steiner-tree-packing min-Steiner-cut theorem
scientific article

    Statements

    An approximate max-Steiner-tree-packing min-Steiner-cut theorem (English)
    0 references
    0 references
    29 May 2008
    0 references
    Given an undirected multigraph \(G\) and a subset of vertices \(S\leq V(G)\), the Steiner tree packing problem is to find a largest collection of edge-disjoint tree that each connect \(S\). \(S\)-cut is a subset of edges whose removal disconnects some vertices in \(S\). We say a graph is \((k-S)\)-connected if every \(S\)-cut has at least \(k\)-edges. Author proves that if \(G\) is \((2k-S)\)-connected, then \(G\) has \(k\)-edge-disjoint trees. The proof is constructive, so if \(G\) is \((26k-S)\)-connected, then a collection of \(k\)-edge-disjoint \(S\)-tree can be constructed in polynomial time. It is a first polynomial time constant factor approximation algorithm for the Steiner tree packing problem.
    0 references
    approximation algorithm trees
    0 references
    Steiner tree packing problem
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references