Length-bounded cuts and flows

DOI10.1145/1868237.1868241MaRDI QIDQ3188986zbMATH OpenOpenAlexWikidataFDO

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

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

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

Recommendations

• Length-Bounded Cuts and Flows
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow
• Parametrized complexity of length-bounded cuts and multi-cuts
• Parameterized complexity of length-bounded cuts and multicuts

Cited in

(37)

• From the separation to the intersection sub-problem in Benders decomposition models with prohibitively-many constraints
• Parameterized complexity of length-bounded cuts and multicuts
• Multiterminal flows and cuts
• The complexity of finding small separators in temporal graphs
• Margin of victory for tournament solutions
• Complexity and algorithms for constant diameter augmentation problems
• Length-bounded cuts: proper interval graphs and structural parameters
• Parsimonious formulations for low-diameter clusters
• On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow
• Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges
• On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths
• New complexity results and algorithms for the minimum tollbooth problem
• Length-Bounded Cuts and Flows
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• scientific article; zbMATH DE number 3950169 (Why is no real title available?)
• 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
• 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
• The complexity of finding small separators in temporal graphs
• On Fault-Tolerant Low-Diameter Clusters in Graphs
• Solving the Distance-Based Critical Node Problem
• On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow
• Minimum violation vertex maps and their applications to cut problems
• The optimal design of low-latency virtual backbones
• The Maximum Flow Problem for Oriented Flows
• scientific article; zbMATH DE number 7758343 (Why is no real title available?)
• scientific article; zbMATH DE number 7765394 (Why is no real title available?)
• Assistance and interdiction problems on interval graphs
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
• Snapshot disjointness in temporal graphs
• Finding conserved low-diameter subgraphs in social and biological networks
• Fitting metrics and ultrametrics with minimum disagreements
• Light edge fault tolerant graph spanners
• Budget and profit approximations for spanning tree interdiction

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188986)