Greedy algorithms for the on-line steiner tree and generalized steiner problems

DOI10.1007/3-540-57155-8_285MaRDI QIDQ5060154zbMATH OpenOpenAlexFDO

Authors Jeffery R. Westbrook, Dicky C. K. Yan

Publication date 18 January 2023

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

Full work available at URL https://doi.org/10.1007/3-540-57155-8_285

Mathematics Subject Classification ID

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

Recommendations

• The Performance of greedy algorithms for the on-line steiner tree and related problems
• The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
• scientific article; zbMATH DE number 1559550
• scientific article; zbMATH DE number 871901
• Non-greedy online Steiner trees on outerplanar graphs

Cites work

• Cost-minimal trees in directed acyclic graphs
• Dynamic Steiner Tree Problem
• scientific article; zbMATH DE number 4010182 (Why is no real title available?)
• On Steiner trees for bounded point sets
• On Steiner’s Problem with Rectilinear Distance
• Reducibility among combinatorial problems
• Steiner problem in networks: A survey

Cited in

(13)

• The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
• Competitive distributed file allocation.
• On-line generalized Steiner problem
• An average case analysis of a greedy algorithm for the on-line Steiner tree problem
• A survey of combinatorial optimization problems in multicast routing
• Non-greedy online Steiner trees on outerplanar graphs
• Non-greedy online Steiner trees on outerplanar graphs
• An O( n)-competitive algorithm for online constrained forest problems
• scientific article; zbMATH DE number 1559550 (Why is no real title available?)
• The sequential sum problem and performance bounds on the greedy algorithm for the on‐line Steiner problem
• The Performance of greedy algorithms for the on-line steiner tree and related problems
• scientific article; zbMATH DE number 871901 (Why is no real title available?)
• On-line Steiner trees in the Euclidean plane

This page was built for publication: Greedy algorithms for the on-line steiner tree and generalized steiner problems

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