TABARIS

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

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element

References in zbMATH (referenced in 16 articles , 1 standard article )

Showing results 1 to 16 of 16.
Sorted by year (citations)

  1. Kizhakkepallathu, Ashik Mathew; Östergård, Patric Rj; Popa, Alexandru: On the Shannon capacity of triangular graphs (2013)
  2. Sewell, E. C.; Jacobson, S. H.; Kaul, Hemanshu: Reductions for the stable set problem (2011)
  3. Grünert, Tore; Irnich, Stefan; Zimmermann, Hans-Jürgen; Schneider, Markus; Wulfhorst, Burkhard: Finding all (k)-cliques in (k)-partite graphs, an application in textile engineering (2002)
  4. Hertz, Alain; Robert, Vincent: Constructing a course schedule by solving a series of assignment type problems (1998)
  5. Osman, Ibrahim H.; Laporte, Gilbert: Metaheuristics: A bibliography (1996)
  6. Soriano, Patrick; Gendreau, Michel: Diversification strategies in tabu search algorithms for the maximum clique problem (1996)
  7. Cao, Buyang; Uebe, Götz: Solving transportation problems with nonlinear side constraints with tabu search (1995)
  8. Costa, Daniel; Hertz, Alain; Dubuis, Olivier: Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs (1995)
  9. Babel, L.: A fast algorithm for the maximum weight clique problem (1994)
  10. Della Croce, Federico; Tadei, Roberto: A multi-KP modeling for the maximum-clique problem (1994)
  11. Pardalos, Panos M.; Xue, Jue: The maximum clique problem (1994)
  12. Dubois, N.; de Werra, Dominique: EPCOT: An efficient procedure for coloring optimally with Tabu Search (1993)
  13. Gendreau, Michel; Soriano, Patrick; Salvail, Louis: Solving the maximum clique problem using a tabu search approach (1993)
  14. Hansen, Pierre; Jaumard, Brigitte: Reduction of indefinite quadratic programs to bilinear programs (1992)
  15. Babel, L.: Finding maximum cliques in arbitrary and in special graphs (1991)
  16. Friden, C.; Hertz, A.; de Werra, Dominique: TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph (1990)