Solving Stability Problems on a Superclass of Interval Graphs

Carlo Mannino (manninodis.uniroma1.it)
Gianpaolo Oriolo (oriolomail.disp.uniroma2.it)

Abstract: 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.

Keywords: Interval Graphs, Stable Sets, Boxicity, Frequency Assignment

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Applications -- OR and Management Sciences (Telecommunications )

Category 3: Other Topics (Dynamic Programming )

Citation: Tech. Rep. Centro Vito Volterra, n. 511, April 2002.

Download: [PDF]

Entry Submitted: 04/18/2002
Entry Accepted: 04/18/2002
Entry Last Modified: 05/06/2002

Modify/Update this entry