1 citations · 1 across the 5 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.CC2015
Advice Complexity of the Online Induced Subgraph Problem
Dennis Komm, Rastislav Královič, Richard Královič +1
Several well-studied graph problems aim to select a largest (or smallest) induced subgraph with a given property of the input graph. Examples of such problems include maximum indep…
cs.DM2015
Adding Isolated Vertices Makes some Online Algorithms Optimal
Joan Boyar, Christian Kudahl
An unexpected difference between online and offline algorithms is observed. The natural greedy algorithms are shown to be worst case online optimal for Online Independent Set and O…