On sequential heurestic methods for the maximum independent set problem | Zendy

Christoph Brause | Zendy; Ngoc C. Lê | Zendy; Ingo Schiermeyer | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On sequential heurestic methods for the maximum independent set problem

Author(s) -

Christoph Brause,

Ngoc C. Lê,

Ingo Schiermeyer

Publication year - 2017

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1965

Subject(s) - mathematics , combinatorics , set (abstract data type) , discrete mathematics , computer science , programming language

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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research