A novel evolutionary formulation of the maximum independent set problem
Authors:
Preprint
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
All Related Versions
- Version 1, 2003-09-22, ArXiv
- Published version: Journal of Combinatorial Optimization, 8 (4), 419.
This publication has 23 references indexed in Scilit:
- On Implementing the Push—Relabel Method for the Maximum Flow ProblemAlgorithmica, 1997
- Solving hard set covering problemsOperations Research Letters, 1995
- Solving the maximum clique problem using a tabu search approachAnnals of Operations Research, 1993
- Test case generators and computational results for the maximum clique problemJournal of Global Optimization, 1993
- A lift-and-project cutting plane algorithm for mixed 0–1 programsMathematical Programming, 1993
- Finding maximum cliques in arbitrary and in special graphsComputing, 1991
- An exact algorithm for the maximum clique problemOperations Research Letters, 1990
- Acyclic orientations of a graph and chromatic and independence numbersJournal of Combinatorial Theory, Series B, 1979
- Acyclic orientations of graphsDiscrete Mathematics, 1973
- Reducibility among Combinatorial Problems1972