1 citations · 1 across the 5 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
cs.DS2014
The Advice Complexity of a Class of Hard Online Problems
Joan Boyar, Lene M. Favrholdt, Christian Kudahl +1
The advice complexity of an online problem is a measure of how much knowledge of the future an online algorithm needs in order to achieve a certain competitive ratio. Using advice…
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.