Linear bounds for on-line Steiner problems

DOI10.1016/0020-0190(95)00000-3zbMath0875.68689OpenAlexW1990065565MaRDI QIDQ672394

Jeffery Westbrook, Dicky C. K. Yan

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00000-3

zbMATH Keywords

Competitive analysisSteiner treesOn-line algorithmsAnalysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

Online Priority Steiner Tree Problems ⋮ A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry ⋮ The Bursty Steiner Tree Problem ⋮ AN OPTIMAL REBUILDING STRATEGY FOR AN INCREMENTAL TREE PROBLEM ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum-weight two-connected spanning networks
• Maintaining bridge-connected and biconnected components on-line
• On the power of randomization in on-line algorithms
• Parallel concepts in graph theory
• Generalized steiner problem in series-parallel networks
• Steiner problem in networks: A survey
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
• The Performance of greedy algorithms for the on-line steiner tree and related problems
• Cost-minimal trees in directed acyclic graphs
• A primal-dual approximation algorithm for generalized Steiner network problems
• Linear‐time algorithms for the 2‐connected steiner subgraph problem on special classes of graphs

This page was built for publication: Linear bounds for on-line Steiner problems