Relaxing the irrevocability requirement for online graph algorithms
DOI10.1007/s00453-022-00944-wzbMath1492.68145arXiv1704.08835OpenAlexW2952999756MaRDI QIDQ5918715
Michal Kotrbčík, Lene Monrad Favrholdt, Kim S. Larsen, Joan. Boyar
Publication date: 28 June 2022
Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.08835
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Online algorithms; streaming algorithms (68W27)
Related Items (6)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online knapsack revisited
- Randomized algorithms for online knapsack problems
- Online minimization knapsack problem
- Competitive snoopy caching
- Online dominating set
- On-line vertex-covering
- Online removable knapsack problem under convex function
- On graph problems in a semi-streaming model
- A linear-time approximation algorithm for weighted matchings in graphs
- The Frequent Items Problem in Online Streaming Under Various Performance Measures
- Improved Bounds for Online Preemptive Matching
- Efficient On-Line Call Control Algorithms
- Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
- The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
- Kuratowski's theorem
- Dynamic Steiner Tree Problem
- An Analysis of the Greedy Heuristic for Independence Systems
- Online Budgeted Maximum Coverage
- Advice Complexity of the Online Induced Subgraph Problem
- Online traveling salesman problems with rejection options
- On the Abstract Properties of Linear Dependence
- Online Maximum Matching with Recourse
- Online Submodular Maximization with Preemption
- Online Steiner Tree with Deletions
- The Power of Recourse for Online MST and TSP
- Relaxing the irrevocability requirement for online graph algorithms
- On the Advice Complexity of Online Edge- and Node-Deletion Problems
This page was built for publication: Relaxing the irrevocability requirement for online graph algorithms
