The shortest multipaths problem in a capacitated dense channel

DOI10.1016/j.ejor.2006.03.007zbMath1163.90703OpenAlexW1978994603MaRDI QIDQ859708

Marie-Christine Costa, Cédric Bentz, Maria Zrikem, Christophe Picouleau

Publication date: 16 January 2007

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2006.03.007

zbMATH Keywords

combinatorial optimizationpolynomial-time algorithmgrid graphcapacitated multipaths problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (2)

An incremental SAT-based approach for solving the real-time taxi-sharing service problem ⋮ Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity

Cites Work

• Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
• Disjoint paths in a rectilinear grid
• Edge-disjoint paths 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
• Bounds and heuristics for the shortest capacitated paths problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Eulerian disjoint paths problem in grid graphs is NP-complete
• Routing through a Dense Channel with Minimum Total Wire Length
• Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids
• Unnamed Item
• Unnamed Item

This page was built for publication: The shortest multipaths problem in a capacitated dense channel