8 citations · 25 across the 28 of their papers we have counts for
4 papers · 2 filters
Batch Coloring of Graphs
Joan Boyar, Leah Epstein, Lene M. Favrholdt +2
In graph coloring problems, the goal is to assign a positive integer color to each vertex of an input graph such that adjacent vertices do not receive the same color assignment. Fo…
Weighted Online Problems with Advice
Joan Boyar, Lene M. Favrholdt, Christian Kudahl +1
Recently, the first online complexity class, AOC, was introduced. The class consists of many online problems where each request must be either accepted or rejected, and the aim is…
Online Dominating Set
Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt +2
This paper is devoted to the online dominating set problem and its variants. We believe the paper represents the first systematic study of the effect of two limitations of online a…
Online Bounded Analysis
Joan Boyar, Leah Epstein, Lene M. Favrholdt +2
Though competitive analysis is often a very good tool for the analysis of online algorithms, sometimes it does not give any insight and sometimes it gives counter-intuitive results…