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

DOI10.1007/978-3-642-38016-7_2zbMATH Open1394.68445OpenAlexW2105378877MaRDI QIDQ2848909FDOQ2848909

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

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

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)

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)