Online independent sets.

DOI10.1016/S0304-3975(01)00411-XzbMath1061.68187MaRDI QIDQ1853575

Shiro Taketomi, Kazuo Iwama, Shuichi Miyazaki, Magnús M. Halldórsson

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Competitive ratioOnline algorithmsIndependent set problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10)

Related Items (15)

A survey on combinatorial optimization in dynamic environments ⋮ Streaming algorithms for independent sets in sparse hypergraphs ⋮ Adding isolated vertices makes some greedy online algorithms optimal ⋮ Online selection of intervals and \(t\)-intervals ⋮ The advice complexity of a class of hard online problems ⋮ Advice complexity of adaptive priority algorithms ⋮ Toward a model for backtracking and dynamic programming ⋮ Parallel online algorithms for the bin packing problem ⋮ Competitive algorithms for multistage online scheduling ⋮ On-line vertex-covering ⋮ On-line maximum-order induced hereditary subgraph problems ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ On-line models and algorithms for max independent set ⋮ Dynamic node packing ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An on-line graph coloring algorithm with sublinear performance ratio
• On-line coloring \(k\)-colorable graphs
• Lower bounds for on-line graph coloring
• Online coloring known graphs
• On-line and first fit colorings of graphs
• Effective coloration

This page was built for publication: Online independent sets.