Approximate Integer Decompositions for Undirected Network Design Problems

Autor:	Chandra Chekuri, F. Bruce Shepherd
Rok vydání:	2009
Předmět:	Discrete mathematics Spanning tree Trémaux tree General Mathematics Rounding Approximation algorithm Eulerian path Robertson–Seymour theorem Combinatorics symbols.namesake symbols Supermodular function Connectivity MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	SIAM Journal on Discrete Mathematics. 23:163-177
ISSN:	1095-7146 0895-4801
DOI:	10.1137/040617339
Popis:	A well-known theorem of Nash-Williams and Tutte gives a necessary and sufficient condition for the existence of $k$ edge-disjoint spanning trees in an undirected graph. A corollary of this theorem is that every $2k$-edge-connected graph has $k$ edge-disjoint spanning trees. We show that the splitting-off theorem of Mader in undirected graphs implies a generalization of this to finding $k$ edge-disjoint Steiner forests in Eulerian graphs. This leads to new 2-approximation rounding algorithms for certain constrained 0-1 forest problems considered by Goemans and Williamson. These algorithms also produce approximate integer decompositions of fractional solutions. We then discuss open problems and outlets for this approach to the more general class of 0-1 skew supermodular network design problems.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::ef209d3840beefe8a4f65c6011a58fb9 https://doi.org/10.1137/040617339 Zobrazit plný text záznamu Plný text ve formátu PDF