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

DOI10.1007/3-540-61332-3_134MaRDI QIDQ6183623zbMATH OpenOpenAlexFDO

Authors Guoliang Xue, Du Ding-Zhu

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

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

Recommendations

• An \(O(n\log n)\) average time algorithm for computing the shortest network under a given topology
• scientific article; zbMATH DE number 1182573
• The shortest network under a given topology
• scientific article; zbMATH DE number 1424545
• An algorithm for the steiner problem in the euclidean plane

Cites work

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

This page was built for publication: O(n log n)-average-time algorithm for shortest network under a given topology

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6183623)