Length-bounded cuts and flows

DOI10.1145/1868237.1868241zbMath1295.68119WikidataQ115954977 ScholiaQ115954977MaRDI QIDQ3188986

Georg Baier, Ekkehard Köhler, Heiko Schilling, Martin Skutella, Erlebach, Thomas, Alexander Hall, Petr Kolman, Ondřej Pangrác

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1868237.1868241

zbMATH Keywords

approximation algorithms; flows and cuts in graphs

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Fractals for Kernelization Lower Bounds, A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths, On Algorithms Employing Treewidth for $L$-bounded Cut Problems, Unnamed Item, On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow, Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing, On the maximum disjoint paths problem on edge-colored graphs, Paths of bounded length and their cuts: parameterized complexity and algorithms, From the separation to the intersection sub-problem in Benders decomposition models with prohibitively-many constraints, Parameterized complexity of length-bounded cuts and multicuts, The complexity of finding small separators in temporal graphs, New Complexity Results and Algorithms for the Minimum Tollbooth Problem, Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms