The point-to-point delivery and connection problems: Complexity and algorithms

DOI10.1016/0166-218X(92)90258-CzbMath0761.68022MaRDI QIDQ1193725

S. Thomas McCormick, David Simchi-Levi, Chung-Lun Li

Publication date: 27 September 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

strongly NP-hard; point-to-point connection problems; point-to-point delivery problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68M10: Network design and communication in computer systems

Related Items

On the point-to-point connection problem, The \(k\)-path tree matroid and its applications to survivable network design, The point-to-point connection problem - analysis and algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of finding two disjoint paths with min-max objective function
• Algorithms for special cases of rectilinear steiner trees: I. Points on the boundary of a rectilinear rectangle
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Rectilinear steiner trees: Efficient special-case algorithms
• On the Complexity of Timetable and Multicommodity Flow Problems
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Routing in Point-to-Point Delivery Systems: Formulations and Solution Heuristics
• Fibonacci heaps and their uses in improved network optimization algorithms
• The steiner problem in graphs