Flow-cut gaps for integer and fractional multiflows

DOI10.1016/j.jctb.2012.11.002zbMath1262.05072OpenAlexW2568140225MaRDI QIDQ1945997

Christophe Weibel, Chandra Chekuri, F. Bruce Shepherd

Publication date: 17 April 2013

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2012.11.002

zbMATH Keywords

network flowsouterplanarmulticommodity flowsinteger flowsseries-parallelflow-cut gapmultiflows

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Distance in graphs (05C12) Flows in graphs (05C21)

Related Items (7)

A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ When Do Gomory--Hu Subtrees Exist? ⋮ Cut-sufficient directed 2-commodity multiflow topologies ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ Unnamed Item ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ Refined Vertex Sparsifiers of Planar Graphs

This page was built for publication: Flow-cut gaps for integer and fractional multiflows