Independent Set with Advice: The Impact of Graph Knowledge

DOI10.1007/978-3-642-38016-7_2zbMath1394.68445OpenAlexW2105378877MaRDI QIDQ2848909

Richard Královič, Stefan Dobrev, Rastislav 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

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) Online algorithms; streaming algorithms (68W27)

Related Items (2)

A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ On the advice complexity of online bipartite matching and online stable marriage

This page was built for publication: Independent Set with Advice: The Impact of Graph Knowledge