Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Independent Sets of Maximum Weight in Apple-Free Graphs
verfasst von : Andreas Brandstädt, Tilo Klembt, Vadim V. Lozin, Raffaele Mosca
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 the first polynomial-time algorithm to solve the Maximum Weight Independent Set problem for apple-free graphs, which is a common generalization of several important classes where the problem can be solved efficiently, such as claw-free graphs, chordal graphs and cographs. Our solution is based on a combination of two algorithmic techniques (modular decomposition and decomposition by clique separators) and a deep combinatorial analysis of the structure of apple-free graphs. Our algorithm is robust in the sense that it does not require the input graph
G
to be apple-free; the algorithm either finds an independent set of maximum weight in
G
or reports that
G
is not apple-free.