Cut-sufficient directed 2-commodity multiflow topologies

DOI10.1007/978-3-031-32726-1_29zbMath1528.90227OpenAlexW4377200039MaRDI QIDQ6086019

F. Bruce Shepherd, Joseph Poremba

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

network flowscutsflow-cut gapmultiflows

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Forbidden directed minors and Kelly-width
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Coarse differentiation and multi-flows in planar graphs
• An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
• Combinatorial approaches to multiflow problems
• The directed subgraph homeomorphism problem
• Multicommodity flows in planar graphs
• Matroids and multicommodity flows
• On max-flow min-cut and integral flow properties for multicommodity flows in directed networks
• Directed tree-width
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The geometry of graphs and some of its algorithmic applications
• Flow-cut gaps for integer and fractional multiflows
• Tournament minors
• Directed tree-width examples
• The Directed Grid Theorem
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Improved approximation for directed cut problems
• Four-terminus flows
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• When Do Gomory--Hu Subtrees Exist?
• On the geometry of graphs with a forbidden minor
• On Constant Multi-Commodity Flow-Cut Gaps for Families of Directed Minor-Free Graphs
• When the cut condition is enough
• Embedding k-Outerplanar Graphs into l1
• Multi-Commodity Network Flows

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