A Novel Evolutionary Formulation of the Maximum Independent Set Problem

Valmir C. Barbosa () and Luciana C. D. Campos
Additional contact information
Valmir C. Barbosa: Universidade Federal do Rio de Janeiro, Programa de Engenharia de Sistemas e Computação
Luciana C. D. Campos: Universidade Federal do Rio de Janeiro, Programa de Engenharia de Sistemas e Computação

Journal of Combinatorial Optimization, 2004, vol. 8, issue 4, No 2, 419-437

Abstract: Abstract We introduce a novel evolutionary formulation of the problem of finding a maximum independent set of a graph. The new formulation is based on the relationship that exists between a graph’s independence number and its acyclic orientations. It views such orientations as individuals and evolves them with the aid of evolutionary operators that are very heavily based on the structure of the graph and its acyclic orientations. The resulting heuristic has been tested on some of the Second DIMACS Implementation Challenge benchmark graphs, and has been found to be competitive when compared to several of the other heuristics that have also been tested on those graphs.

Keywords: maximum independent sets; evolutionary algorithms; genetic algorithms (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-004-4835-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:8:y:2004:i:4:d:10.1007_s10878-004-4835-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-004-4835-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().