Some classical combinatorial problems on circulant and claw-free graphs: the isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs |
| |
Authors: | Ugo Pietropaoli |
| |
Institution: | 1. Dipartimento di Statistica Probabilità e Statistiche Applicate, Sapienza Università di Roma, P.le Aldo Moro, 5, 00185, Rome, Italy 2. Dipartimento di Ingegneria dell’Impresa, Università di Roma Tor Vergata, Via del Politecnico, 1, 00133, Rome, Italy
|
| |
Abstract: | This is a summary of the author’s Ph.D. thesis supervised by Sara Nicoloso and Gianpaolo Oriolo and defended on 3 April 2008 at
Sapienza Università di Roma. The thesis is written in English and is available from the author upon request. This work deals
with three classical combinatorial problems, namely the isomorphism, the vertex-coloring and the stable set problem, restricted
to two graph classes, namely circulant and claw-free graphs. In the first part (joint work with Sara Nicoloso), we derive a necessary and sufficient condition to test isomorphism
of circulant graphs, and give simple algorithms to solve the vertex-coloring problem on this class of graphs. In the second
part (joint work with Gianpaolo Oriolo and Gautier Stauffer), we propose a new combinatorial algorithm for the maximum weighted
stable set problem in claw-free graphs, and devise a robust algorithm for the same problem in the subclass of fuzzy circular
interval graphs, which also provides recognition when the stability number is greater than three. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|