Optimization Online


Solving Stability Problems on a Superclass of Interval Graphs

Carlo Mannino (mannino***at***dis.uniroma1.it)
Gianpaolo Oriolo (oriolo***at***mail.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society