The point-to-point connection problem - analysis and algorithms

DOI10.1016/S0166-218X(97)00010-3zbMath0890.68104MaRDI QIDQ1377667

Madan Natu, Shu-Cherng Fang

Publication date: 11 June 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

time complexityDijkstra-like algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Related Items

Augmenting weighted graphs to establish directed point-to-point connectivity, Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs, The \(k\)-path tree matroid and its applications to survivable network design, Parameterized certificate dispersal and its variants, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the point-to-point connection problem
• The point-to-point delivery and connection problems: Complexity and algorithms
• The Steiner tree problem
• An efficiently solvable case of the minimum weight equivalent subgraph problem
• Finding a minimum equivalent graph of a digraph
• Routing in Point-to-Point Delivery Systems: Formulations and Solution Heuristics
• Fibonacci heaps and their uses in improved network optimization algorithms
• Steiner's problem in graphs and its implications
• The steiner problem in graphs