A novel evolutionary formulation of the maximum independent set problem

DOI10.1007/S10878-004-4835-9MaRDI QIDQ1777419zbMATH OpenOpenAlexWikidataFDO

Authors Valmir C. Barbosa, Luciana C. D. Campos

Publication date 13 May 2005

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0309038

zbMATH Keywords

genetic algorithmsevolutionary algorithmsmaximum independent sets

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

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.

Recommendations

• Two novel evolutionary formulations of the graph coloring problem
• An unconstrained binary quadratic programming for the maximum independent set problem
• Finding independent sets in a graph using continuous multivariable polynomial formulations.
• A new heuristic algorithm to solve the maximum independent set problem
• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere

Cited in

(8)

• An adaptive multistart tabu search approach to solve the maximum clique problem
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers
• Two novel evolutionary formulations of the graph coloring problem
• scientific article; zbMATH DE number 1961986 (Why is no real title available?)
• An efficient local search framework for the minimum weighted vertex cover problem
• A relation-algebraic view on evolutionary algorithms for some graph problems
• Optimization of supply diversity for the self-assembly of simple objects in two and three dimensions

Describes a project that uses

Uses Software

• QUALEX
• DIMACS

This page was built for publication: A novel evolutionary formulation of the maximum independent set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1777419)