PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2017 | 37 | 2 | 415-426
Tytuł artykułu

On Sequential Heuristic Methods for the Maximum Independent Set Problem

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
We consider sequential heuristics methods for the Maximum Independent Set (MIS) problem. Three classical algorithms, VO [11], MIN [12], or MAX [6] , are revisited. We combine Algorithm MIN with the α-redundant vertex technique[3]. Induced forbidden subgraph sets, under which the algorithms give maximum independent sets, are described. The Caro-Wei bound [4,14] is verified and performance of the algorithms on some special graphs is considered.
Słowa kluczowe
Wydawca
Rocznik
Tom
37
Numer
2
Strony
415-426
Opis fizyczny
Daty
wydano
2017-05-01
otrzymano
2015-12-29
poprawiono
2017-02-01
zaakceptowano
2017-02-01
online
2017-04-01
Twórcy
autor
  • Faculty of Mathematics and Computer Science Technische Universität Bergakademie Freiberg School of Applied Mathematics and Informatics Hanoi University of Science and Technology,, lechingoc@yahoo.com
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1965
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.