Length-bounded cuts and flows

DOI10.1145/1868237.1868241zbMath1295.68119OpenAlexW2025838844WikidataQ115954977 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 algorithmsflows and cuts in graphs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (27)

Length-bounded cuts: proper interval graphs and structural parameters ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ New Complexity Results and Algorithms for the Minimum Tollbooth Problem ⋮ From the separation to the intersection sub-problem in Benders decomposition models with prohibitively-many constraints ⋮ Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing ⋮ Solving the Distance-Based Critical Node Problem ⋮ Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges ⋮ Assistance and interdiction problems on interval graphs ⋮ On the maximum disjoint paths problem on edge-colored graphs ⋮ On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow ⋮ Fractals for Kernelization Lower Bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Maximum Flow Problem for Oriented Flows ⋮ Paths of bounded length and their cuts: parameterized complexity and algorithms ⋮ Parsimonious formulations for low-diameter clusters ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ The complexity of finding small separators in temporal graphs ⋮ Parameterized complexity of length-bounded cuts and multicuts ⋮ On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths ⋮ Margin of victory for tournament solutions ⋮ Complexity and algorithms for constant diameter augmentation problems ⋮ Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms

This page was built for publication: Length-bounded cuts and flows