|
|||||
|
|
Feedback vertex set on AT-free graphs |
|
| Authors: | Dieter Kratsch |
| Institution: | a Laboratoire d’Informatique Théorique et Appliquée, Université de Metz, 57045 Metz Cedex 01, France b School of Computing, University of Leeds, Leeds LS2 9JT, UK c Laboratoire d’Informatique Fondamentale d’Orléans (LIFO), Université d’Orléans, BP 6759, 45067 Orléans Cedex 2, France |
| Abstract: | We present a polynomial time algorithm to compute a minimum (weight) feedback vertex set for AT-free graphs, and extending this approach we obtain a polynomial time algorithm for graphs of bounded asteroidal number. |
| Keywords: | Feedback vertex set Asteroidal triple-free graph |
| 本文献已被 ScienceDirect 等数据库收录！ | |