Multiflow Feasibility: An Annotated Tableau

DOI10.1007/978-3-540-76796-1_12zbMath1359.90159OpenAlexW30616553MaRDI QIDQ2971612

Guyslain Naves, András Sebő

Publication date: 7 April 2017

Published in: Research Trends in Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-76796-1_12

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (9)

Combing a Linkage in an Annulus ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs ⋮ Multiflows in symmetric digraphs ⋮ Max-multiflow/min-multicut for G+H series-parallel ⋮ Walking through waypoints ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Euler Digraphs

Cites Work

• The hardness of routing two pairs on one face
• Minimal multicut and maximal integer multiflow: a survey
• Packing paths in planar graphs
• The Klein bottle and multicommodity flows
• Combinatorial approaches to multiflow problems
• The directed subgraph homeomorphism problem
• Multicommodity flows in planar graphs
• Paths, flows, and VLSI-layout. Proceedings of a meeting held from June 20 to July 1, 1988, at the University of Bonn, Germany
• Integer plane multiflows with a mixed number of demands
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Eulerian disjoint paths problem in grid graphs is NP-complete
• Graph minors. XIII: The disjoint paths problem
• NP-completeness of some edge-disjoint paths problems
• On the complexity of the disjoint paths problem
• On the complexity of the planar directed edge-disjoint paths problem
• On Odd Cuts and Plane Multicommodity Flows
• On the Computational Complexity of Combinatorial Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• A Minimax Theorem for Directed Graphs
• Finding k Disjoint Paths in a Directed Planar Graph
• Feasibility of Two Commodity Network Flows
• Weak Three-Linking in Eulerian Dgraphs
• Combinatorial optimization. Theory and algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Multiflow Feasibility: An Annotated Tableau