Non-greedy online Steiner trees on outerplanar graphs

DOI10.1007/s00453-020-00768-6zbMath1484.68343OpenAlexW3092788214MaRDI QIDQ2659774

Akira Matsubayashi

Publication date: 26 March 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-020-00768-6

zbMATH Keywords

competitive analysisonline algorithmSteiner treeouterplanar graph

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• On-line Steiner trees in the Euclidean plane
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Competitive algorithms for distributed data management.
• On the power of randomization in on-line algorithms
• Competitive distributed file allocation.
• On-line generalized Steiner problem
• Online Priority Steiner Tree Problems
• On the Competitiveness of the Online Asymmetric and Euclidean Steiner Tree Problems
• Dynamic Steiner Tree Problem
• Competitive On-Line Algorithms for Distributed Data Management
• The Performance of greedy algorithms for the on-line steiner tree and related problems
• Embedding k-Outerplanar Graphs into l1
• Online Node-Weighted Steiner Tree and Related Problems

This page was built for publication: Non-greedy online Steiner trees on outerplanar graphs