Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Finding cuts and separators
verfasst von : Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Erschienen in: Parameterized Algorithms
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
The notion of important cuts and the related combinatorial bounds give a useful tool for showing the fixed-parameter tractability of problems where a graph has to be cut into certain parts. We discuss how this technique can be used to show that
E
dge
M
ultiway
C
ut
and
D
irected
F
eedback
V
ertex
S
et
are FPT. Random sampling of important separators is a recent extension of this method, making it applicable to a wider range of problems. We illustrate how this extension works on a clustering problem called (p, q)-
P
artition
.