Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Extending the MAX Algorithm for Maximum Independent Set

Ngoc C. Lê;  Christoph Brause;  Ingo Schiermeyer — 2015

Discussiones Mathematicae Graph Theory

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.

On Sequential Heuristic Methods for the Maximum Independent Set Problem

Ngoc C. Lê;  Christoph Brause;  Ingo Schiermeyer — 2017

Discussiones Mathematicae Graph Theory

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.

Page 1

Download Results (CSV)