O(n log n)-average-time algorithm for shortest network under a given topology

DOI10.1007/3-540-61332-3_134zbMath1529.68230OpenAlexW1560570792MaRDI QIDQ6183623

Ding-Zhu Du, Guoliang Xue

Publication date: 29 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61332-3_134

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• A linear time algorithm for full Steiner trees
• Exact computation of Steiner minimal trees in the plane
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• The Steiner tree problem
• An 11/6-approximation algorithm for the network Steiner problem
• On the Problem of Steiner
• An Improved Algorithm for Steiner Trees
• An algorithm for the steiner problem in the euclidean plane
• The shortest network under a given topology
• The Complexity of Computing Steiner Minimal Trees
• Steiner Minimal Trees