Independent set with advice: the impact of graph knowledge (extended abstract)

DOI10.1007/978-3-642-38016-7_2MaRDI QIDQ2848909zbMATH OpenOpenAlexFDO

Authors Stefan Dobrev, Rastislav Královič, Richard Královič

Publication date 13 September 2013

Published in Approximation and Online Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Advice complexity of maximum independent set in sparse and bipartite graphs
• Advice complexity for a class of online problems
• Advice complexity of the online induced subgraph problem
• The advice complexity of a class of hard online problems
• On the advice complexity of the online dominating set problem

Cited in

(4)

• On the advice complexity of online bipartite matching and online stable marriage
• A technique to obtain hardness results for randomized online algorithms -- a survey
• Advice complexity of the online induced subgraph problem
• Further results on online node- and edge-deletion problems with advice

This page was built for publication: Independent set with advice: the impact of graph knowledge (extended abstract)

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