Extending the Max Algorithm for maximum independent set | Zendy

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

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Extending the Max Algorithm for maximum independent set

Author(s) -

Christoph Brause,

Ngoc C. Lê,

Ingo Schiermeyer

Publication year - 2015

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.1811

Subject(s) - independent set , mathematics , combinatorics , set (abstract data type) , graph , maximal independent set , algorithm , time complexity , discrete mathematics , computer science , pathwidth , line graph , programming language

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

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