The stable set problem and the thinness of a graph

The stable set problem and the thinness of a graph

0.00 Avg rating0 Votes
Article ID: iaor20073056
Country: Netherlands
Volume: 35
Issue: 1
Start Page Number: 1
End Page Number: 9
Publication Date: Jan 2007
Journal: Operations Research Letters
Authors: , , ,
Keywords: sets
Abstract:

We introduce a poly-time algorithm for the maximum weighted stable set problem, when a certain representation is given for a graph. The algorithm generalizes the algorithm for interval graphs and that for graphs with bounded pathwidth. By a suitable application to the frequency assignment problem, we improved several solutions to relevant benchmark instances.

Reviews

Required fields are marked *. Your email address will not be published.