Extending the MAX Algorithm for Maximum Independent Set

Szczegóły
Opis

Tytuł:: Extending the MAX Algorithm for Maximum Independent Set
Autorzy:: Lê, Ngoc C.
Brause, Christoph
Schiermeyer, Ingo
Powiązania:: https://bibliotekanauki.pl/articles/31339469.pdf
Data publikacji:: 2015-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: maximum independent set
stable set
stability number
independence number
reduction
graph transformation
MAX Algorithm
MIN Algorithm
Vertex Order Algorithm
Źródło:: Discussiones Mathematicae Graph Theory; 2015, 35, 2; 365-386
2083-5892
Język:: angielski
Prawa:: CC BY-NC-ND: Creative Commons Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 4.0
Dostawca treści:: Biblioteka Nauki
: Artykuł

Przejdź do źródła

The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.

Informacja

Powiązane pozycje