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

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

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

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

Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), Online Node-weighted Steiner Forest and Extensions via Disk Paintings, Parameterized certificate dispersal and its variants, 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, Linkage on the infinite grid, Augmenting weighted graphs to establish directed point-to-point connectivity

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