We introduce a graph invariant, called thinness, and show that a maximum weighted stable set on a graph $G(V, E)$ with thinness $k$ may be found in $O(\frac{|V|}{k})^k$-time, if a certain representation is given. We show that a graph has thinness 1 if and only if it is an interval graph, while a graph with thinness $k$ is the intersection graph of $k$-dimensional boxes. We investigate properties of the thinness and discuss relationships between graphs with thinness at most two and other superclasses of interval graphs. We present real a world application where suitable graphs with small thinness naturally occur: the frequency assignment problem ({\sc fap}). We show that an efficient search in exponential neighbourhoods for {\sc fap} may be done by our polynomial time algorithm. This led us to improving the best known solutions for some benchmark instances of {\sc fap} in {\sc gsm} networks. We discuss other applications where a same approach seems quite natural, among which the single machine scheduling problem. We leave some open questions.
Citation
Tech. Rep. Centro Vito Volterra, n. 511, April 2002.
Article
View Solving Stability Problems on a Superclass of Interval Graphs