Adding isolated vertices makes some greedy online algorithms optimal

DOI10.1016/j.dam.2017.02.025zbMath1390.05223arXiv1506.08592OpenAlexW2600162651MaRDI QIDQ1647831

Christian Kudahl, Joan. Boyar

Publication date: 27 June 2018

Published in: Discrete Applied Mathematics, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.08592

zbMATH Keywords

greedy algorithmonline algorithmsisolated verticesonline independence number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online chromatic number is PSPACE-complete
• On domination and independent domination numbers of a graph
• An on-line graph coloring algorithm with sublinear performance ratio
• On-line vertex-covering
• Online independent sets.
• The relative worst order ratio for online algorithms
• Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete
• Randomized online graph coloring
• On-line maximum-order induced hereditary subgraph problems
• On-Line 3-Chromatic Graphs I. Triangle-Free Graphs

This page was built for publication: Adding isolated vertices makes some greedy online algorithms optimal