- 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/2002Entry Accepted: 04/18/2002Entry Last Modified: 05/06/2002Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.