Online independent sets.

DOI10.1016/S0304-3975(01)00411-XMaRDI QIDQ1853575zbMATH OpenFDO

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

Publication date 21 January 2003

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

Full work available at URL https://doi.org/10.1016/S0304-3975(01)00411-X

zbMATH Keywords

Competitive ratioIndependent set problemOnline algorithms

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1696636
• Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
• On-line models and algorithms for max independent set
• Online independent set beyond the worst-case: secretaries, prophets, and periods
• scientific article; zbMATH DE number 5842466

Cites work

• An on-line graph coloring algorithm with sublinear performance ratio
• Effective coloration
• scientific article; zbMATH DE number 1003261 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• Lower bounds for on-line graph coloring
• On-line and first fit colorings of graphs
• On-line coloring \(k\)-colorable graphs
• Online coloring known graphs

Cited in

(19)

• The advice complexity of a class of hard online problems
• Competitive algorithms for multistage online scheduling
• On-line vertex-covering
• Dynamic node packing
• Advice complexity of maximum independent set in sparse and bipartite graphs
• Parallel online algorithms for the bin packing problem
• scientific article; zbMATH DE number 1696636 (Why is no real title available?)
• A survey on combinatorial optimization in dynamic environments
• Streaming algorithms for independent sets in sparse hypergraphs
• On-line models and algorithms for max independent set
• Online selection of intervals and t-intervals
• Toward a model for backtracking and dynamic programming
• On-line maximum-order induced hereditary subgraph problems
• scientific article; zbMATH DE number 1418264 (Why is no real title available?)
• Online independent set beyond the worst-case: secretaries, prophets, and periods
• Advice complexity of adaptive priority algorithms
• Comparing the hardness of online minimization and maximization problems with predictions
• Stable approximation algorithms for dominating set and independent set
• Random-order online independent set of intervals and hyperrectangles

This page was built for publication: Online independent sets.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853575)