2 papers
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…
math.CO2010
Contracting planar graphs to contractions of triangulations
Marcin Kaminski, Daniel Paulusma, Dimitrios M. Thilikos
For every graph , there exists a polynomial-time algorithm deciding if a planar input graph can be contracted to~. However, the degree of the polynomial depends on the si…