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. (c) 2006 Elsevier B.V. All rights reserved.
The stable set problem and the thinness of a graph / Mannino, Carlo; Gianpaolo, Oriolo; RICCI TERSENGHI, Federico; Sunil, Chandran. - In: OPERATIONS RESEARCH LETTERS. - ISSN 0167-6377. - 35:1(2007), pp. 1-9. [10.1016/j.orl.2006.01.009]
The stable set problem and the thinness of a graph
MANNINO, Carlo;RICCI TERSENGHI, Federico;
2007
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. (c) 2006 Elsevier B.V. All rights reserved.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
