Adding isolated vertices makes some greedy online algorithms optimal

DOI10.1016/J.DAM.2017.02.025MaRDI QIDQ6827500zbMATH OpenFDO

Authors Joan Boyar, Christian Kudahl

Publication date 27 June 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

online algorithmsgreedy algorithmisolated verticesonline independence number

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

This page was built for publication: Adding isolated vertices makes some greedy online algorithms optimal

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