  


Solving Stability Problems on a Superclass of Interval Graphs
Carlo Mannino (manninodis.uniroma1.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 Modify/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  