Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Improved Fixed-Parameter Algorithms for Two Feedback Set Problems
verfasst von : Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, Sebastian Wernicke
Erschienen in: Algorithms and Data Structures
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Settling a ten years open question, we show that the NP-complete
Feedback Vertex Set
problem is deterministically solvable in
O
(
c
k
·
m
) time, where
m
denotes the number of graph edges,
k
denotes the size of the feedback vertex set searched for, and
c
is a constant. As a second result, we present a fixed-parameter algorithm for the NP-complete
Edge Bipartization
problem with runtime
O
(2
k
·
m
2
).