Advice Complexity of the Online Induced Subgraph Problem

DOI10.4230/LIPIcs.MFCS.2016.59zbMath1398.68691arXiv1512.05996OpenAlexW2962942578MaRDI QIDQ4608622

Christian Kudahl, Richard Královič, Dennis Komm, Rastislav Královič

Publication date: 21 March 2018

Full work available at URL: https://arxiv.org/abs/1512.05996

zbMATH Keywords

online algorithmsadvice complexityinduced subgraph problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items (6)

Further Results on Online Node- and Edge-Deletion Problems with Advice ⋮ On the Advice Complexity of Online Edge- and Node-Deletion Problems ⋮ Advice complexity of adaptive priority algorithms ⋮ Online node- and edge-deletion problems with advice ⋮ Weighted online problems with advice ⋮ Relaxing the irrevocability requirement for online graph algorithms

This page was built for publication: Advice Complexity of the Online Induced Subgraph Problem