swMATH ID: 2534
Software Authors: Friden, C.; Hertz, A.; de Werra, Dominique
Description: TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph. A technique for finding in a graph an independent set with maximum cardinality is presented. It consists of an implicit enumeration procedure; the procedure uses at various stages bounds on the independence number of a subgraph. These are obtained by applying an adaptation of Tabu Search. Computational results are given which show that with Tabu Search a competitive algorithm is obtained; the case of randomly generated graphs having up to 450 or 500 nodes (with edge density 0.5) can be handled by this approach
Homepage: http://www.sciencedirect.com/science/article/pii/030505489090048C
Keywords: maximum independent set in a graph; computational comparison of algorithms; Balas-Yu algorithm; exact implicit enumeration; Tabu Search; TABARIS; heuristic; STABULARGE; random graphs
Related Software: Algorithm 457; Tabu search; DIMACS; Cliquer; NISPOC; nauty; Genocop; Sugal; ILOG SCHEDULE; GIDEON; OR-Library
Cited in: 16 Publications

Citations by Year