Linear bounds for on-line Steiner problems

DOI10.1016/0020-0190(95)00000-3MaRDI QIDQ672394zbMATH OpenOpenAlexFDO

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

Publication date 28 February 1997

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

Analysis of algorithmsCompetitive analysisOn-line algorithmsSteiner trees

Mathematics Subject Classification ID

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

Cites work

• A primal-dual approximation algorithm for generalized Steiner network problems
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
• Cost-minimal trees in directed acyclic graphs
• Generalized steiner problem in series-parallel networks
• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 4010182 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 742977 (Why is no real title available?)
• Linear‐time algorithms for the 2‐connected steiner subgraph problem on special classes of graphs
• Maintaining bridge-connected and biconnected components on-line
• Minimum-weight two-connected spanning networks
• On the power of randomization in on-line algorithms
• Parallel concepts in graph theory
• Steiner problem in networks: A survey
• The Performance of greedy algorithms for the on-line steiner tree and related problems

Cited in

(7)

• On-line generalized Steiner problem
• Parameterized analysis of the online priority and node-weighted Steiner tree problems
• scientific article; zbMATH DE number 6381651 (Why is no real title available?)
• Online Priority Steiner Tree Problems
• A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry
• AN OPTIMAL REBUILDING STRATEGY FOR AN INCREMENTAL TREE PROBLEM
• The bursty Steiner tree problem

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

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