Cut-sufficient directed 2-commodity multiflow topologies

DOI10.1007/978-3-031-32726-1_29MaRDI QIDQ6086019zbMATH OpenOpenAlexFDO

Authors Joseph Poremba, F. Bruce Shepherd

Publication date 9 November 2023

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-32726-1_29

zbMATH Keywords

cutsflow-cut gapmultiflowsnetwork flows

Mathematics Subject Classification ID

Flows in graphs (05C21) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• When the cut condition is enough, a complete characterization for multiflow problems in series-parallel networks
• On max-flow min-cut and integral flow properties for multicommodity flows in directed networks
• On duality and fractionality of multicommodity flows in directed networks
• Combinatorial approaches to multiflow problems
• scientific article; zbMATH DE number 66623

Cites work

• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• An O( n)-approximation algorithm for directed sparsest cut
• Coarse differentiation and multi-flows in planar graphs
• Combinatorial approaches to multiflow problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Directed nowhere dense classes of graphs
• Directed tree-width
• Directed tree-width examples
• Embedding k-Outerplanar Graphs into l1
• Flow-cut gaps for integer and fractional multiflows
• Forbidden directed minors and Kelly-width
• Four-terminus flows
• scientific article; zbMATH DE number 7378361 (Why is no real title available?)
• Improved approximation for directed cut problems
• Matroids and multicommodity flows
• Multi-Commodity Network Flows
• Multicommodity flows in planar graphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On constant multi-commodity flow-cut gaps for families of directed minor-free graphs
• On max-flow min-cut and integral flow properties for multicommodity flows in directed networks
• On the geometry of graphs with a forbidden minor
• The directed grid theorem
• The directed subgraph homeomorphism problem
• The geometry of graphs and some of its algorithmic applications
• Tournament minors
• When do Gomory-Hu subtrees exist?
• When the cut condition is enough, a complete characterization for multiflow problems in series-parallel networks

Cited in

(2)

• Integer and unsplittable multiflows in series-parallel digraphs
• Combinatorial optimization. Abstracts from the workshop held November 10--15, 2024

This page was built for publication: Cut-sufficient directed 2-commodity multiflow topologies

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