The stable set problem and the thinness of a graph |
| |
| Authors: | Carlo Mannino Gianpaolo Oriolo Federico Ricci Sunil Chandran |
| |
| Affiliation: | Dip. di Informatica e Sistemistica, Universita di Roma, ‘La Spapienza’, Via Bounarroti 12, I-00185 Roma, Italy |
| |
| 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. |
| |
| Keywords: | Thinness Stable set Frequency assignment Pathwidth |
| 本文献已被 ScienceDirect 等数据库收录！ |
