3 citations · 5 across the 10 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2023
Online Graph Coloring with Predictions
Antonios Antoniadis, Hajo Broersma, Yang Meng
We introduce learning augmented algorithms to the online graph coloring problem. Although the simple greedy algorithm FirstFit is known to perform poorly in the worst case, we are…
cs.DS2013
Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
Hajo Broersma, Jiří Fiala, Petr A. Golovach +3
Hung and Chang showed that for all k>=1 an interval graph has a path cover of size at most k if and only if its scattering number is at most k. They also showed that an interval gr…