Length-Bounded Cuts and Flows

Simple item page
dc.contributor.authorBaier, Georg
dc.contributor.authorErlebach, Thomas
dc.contributor.authorHall, Alexander
dc.contributor.authorKöhler, Ekkehard
dc.contributor.authorSchilling, Heiko
dc.contributor.authorSkutella, Martin
dc.date.accessioned2021-12-17T10:07:08Z
dc.date.available2021-12-17T10:07:08Z
dc.date.issued2006
dc.description.abstractAn L-length-bounded cut in a graph G with source s, and sink t is a cut that destroys all s-t-paths of length at most L. An L-length-bounded flow is a flow in which only flow paths of length at most L are used. The first research on path related constraints we are aware of was done in 1978 by Lovász, Neumann Lara, and Plummer. Among others they show that the minimum length-bounded node-cut problem is polynomial for L≤4. We show that the minimum length-bounded cut problem turns out to be NP-hard to approximate within a factor of 1.1377 for L≥5 in the case of node-cuts and for L≥4 in the case of edge-cuts (both in graphs with unit edge lengths). We also give approximation algorithms of ratio min{L,n/L} in the node case and min{L,n2/L2,√m} in the edge case, where n denotes the number of nodes and m denotes the number of edges. For classes of graphs such as constant degree expanders, hypercubes, and butterflies, we obtain O(log n)-approximations by using the Shortening Lemma for flow numbers [Kolman and Scheideler, SODA'02]. We discuss the integrality gaps of the LP relaxations of length-bounded flow and cut problems, which can be of size Ω(√n). We show that edge- and path-flows are not polynomially equivalent for length-bounded flows, analyze the structure of optimal solutions and give instances where each maximum flow ships a large percentage of the flow along paths with an arbitrarily small flow value.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15600
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14373
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherapproximation algorithmsen
dc.subject.otherhardness of approximationen
dc.subject.otherlength-bounded cutsen
dc.subject.otherlength-bounded edge-disjoint pathsen
dc.subject.othermulti-commodity flowsen
dc.titleLength-Bounded Cuts and Flowsen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2006, 05en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.subject.msc200068R10 Graph theoryen
tub.subject.msc200090C27 Combinatorial optimizationen
tub.subject.msc200068W25 Approximation algorithmsen
tub.subject.msc200068Q25 Analysis of algorithms and problem complexityen
tub.subject.msc200005C85 Graph algorithmsen

Files

Original bundle
Now showing 1 - 4 of 4
Thumbnail Image
Name:
Report-005-2006.pdf
Size:
250.07 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
Report-005-2006.ps.bz2
Size:
174.62 KB
Format:
Unknown data format
Download
No Thumbnail Available
Name:
Report-005-2006.ps.gz
Size:
204.31 KB
Format:
Unknown data format
Download
No Thumbnail Available
Name:
Report-005-2006.ps
Size:
517.79 KB
Format:
Postscript Files
Download

Collections

Publications