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…