2008 | OriginalPaper | Buchkapitel
Faster Parameterized Algorithms for Minimum Fill-In
verfasst von : Hans L. Bodlaender, Pinar Heggernes, Yngve Villanger
Erschienen in: Algorithms and Computation
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
We present two parameterized algorithms for the
Minimum Fill-In
problem, also known as
Chordal Completion
: given an arbitrary graph
G
and integer
k
, can we add at most
k
edges to
G
to obtain a chordal graph? Our first algorithm has running time
, and requires polynomial space. This improves the base of the exponential part of the best known parameterized algorithm time for this problem so far. We are able to improve this running time even further, at the cost of more space. Our second algorithm has running time
and requires
space.