Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Algorithms Parameterized by Vertex Cover and Modular Width, through Potential Maximal Cliques
verfasst von : Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre, Ioan Todinca
Erschienen in: Algorithm Theory – SWAT 2014
Verlag: Springer International Publishing
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
In this paper we give upper bounds on the number of
minimal separators
and
potential maximal cliques of graphs
w.r.t. two graph parameters, namely
vertex cover
(vc) and
modular width
(mw). We prove that for any graph, the number of minimal separators is
$\mathcal{O}^*(3^{\operatorname{vc}})$
and
$\mathcal{O}^*(1.6181^{\operatorname{mw}})$
, the number of potential maximal cliques is
$\mathcal{O}^*(4^{\operatorname{vc}})$
and
$\mathcal{O}^*(1.7347^{\operatorname{mw}})$
, and these objects can be listed within the same running times. (The
$\mathcal{O}^*$
notation suppresses polynomial factors in the size of the input.) Combined with known results [3,12], we deduce that a large family of problems, e.g.,
Treewidth
,
Minimum Fill-in
,
Longest Induced Path
,
Feedback vertex set
and many others, can be solved in time
$\mathcal{O}^*(4^{\operatorname{vc}})$
or
$\mathcal{O}^*(1.7347^{\operatorname{mw}})$
.