Feedback Vertex Set and Longest Induced Path on AT-Free Graphs

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 algorithm for graphs of bounded asteroidal number. We also present an O(nm) algorithm to compute a longest induced path in AT-free graphs.

Data and Resources

Additional Info

Field Value
Source 29th International Workshop on Graph-Theoretic Concepts in Computer Science
Author Kratsch, Dieter, Müller, Haiko, Todinca, Ioan
Maintainer CCSD
Last Updated May 9, 2026, 23:26 (UTC)
Created May 9, 2026, 23:26 (UTC)
Identifier hal-00085560
Language en
contributor Laboratoire d'Informatique Fondamentale d'Orléans (LIFO) ; Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges
creator Kratsch, Dieter
date 2003-05-09T00:00:00
harvest_object_id 65e646b3-1c6b-4e5b-9289-3d2a0209e518
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-08-12T00:00:00
set_spec type:COMM