An O(logn)-Competitive Algorithm for Online Constrained Forest Problems

DOI10.1007/978-3-642-22006-7_4zbMath1332.68296OpenAlexW1517384480MaRDI QIDQ3012790

Jiawei Qian, David P. Williamson

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_4

Mathematics Subject Classification ID

Trees (05C05) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Related Items (4)

From Cost Sharing Mechanisms to Online Selection Problems ⋮ Unnamed Item ⋮ Online constrained forest and prize-collecting network design ⋮ Online Node-weighted Steiner Forest and Extensions via Disk Paintings

Cites Work

• Unnamed Item
• Unnamed Item
• On-line generalized Steiner problem
• A primal-dual approximation algorithm for generalized Steiner network problems
• Dynamic Steiner Tree Problem
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Online and stochastic survivable network design

This page was built for publication: An O(logn)-Competitive Algorithm for Online Constrained Forest Problems