An approximate max-Steiner-tree-packing min-Steiner-cut theorem (Q925137): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00493-007-0044-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2097945626 / rank | |||
Normal rank |
Latest revision as of 22:20, 19 March 2024
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
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