1 citations · 1 across the 5 of their papers we have counts for
Showing cs.CCShow 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.CC2014★ 1 cited
Deciding the On-line Chromatic Number of a Graph with Pre-Coloring is PSPACE-Complete
Christian Kudahl
The problem of determining if the on-line chromatic number of a graph is less than or equal to k, given a pre-coloring, is shown to be PSPACE-complete.