TABARIS 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 Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph. Zbl 0713.90087Friden, C.; Hertz, A.; de Werra, Dominique 1990 all top 5 Cited by 32 Authors 3 Hertz, Alain 2 Babel, Luitpold 2 de Werra, Dominique 2 Gendreau, Michel 2 Soriano, Patrick 1 Cao, Buyang 1 Costa, Daniel G. 1 Della Croce, Federico 1 Dubois, Nicolas 1 Dubuis, Olivier 1 Friden, C. 1 Grünert, Tore 1 Hansen, Pierre 1 Irnich, Stefan 1 Jacobson, Sheldon H. 1 Jaumard, Brigitte 1 Kaul, Hemanshu 1 Kizhakkepallathu, Ashik Mathew 1 Laporte, Gilbert 1 Osman, Ibrahim Hassan 1 Östergård, Patric Rj 1 Pardalos, Panos M. 1 Popa, Alexandru 1 Robert, Vincent 1 Salvail, Louis 1 Schneider, Markus 1 Sewell, Edward C. 1 Tadei, Roberto 1 Uebe, Götz 1 Wulfhorst, Burkhard 1 Xue, Jue 1 Zimmermann, Hans-Jürgen all top 5 Cited in 9 Serials 3 Computers & Operations Research 3 Annals of Operations Research 2 Computing 2 Journal of Global Optimization 2 European Journal of Operational Research 1 Computers & Mathematics with Applications 1 The Electronic Journal of Combinatorics 1 Journal of Heuristics 1 Algorithmic Operations Research all top 5 Cited in 6 Fields 11 Operations research, mathematical programming (90-XX) 7 Combinatorics (05-XX) 4 Computer science (68-XX) 1 Numerical analysis (65-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year