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


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)