TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph

DOI10.1016/0305-0548(90)90048-CzbMath0713.90087OpenAlexW2048440507MaRDI QIDQ750320

C. Friden, Dominique de Werra, Alain Hertz

Publication date: 1990

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0305-0548(90)90048-c

zbMATH Keywords

random graphsheuristicTabu SearchBalas-Yu algorithmcomputational comparison of algorithmsexact implicit enumerationmaximum independent set in a graphSTABULARGETABARIS

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Combinatorial optimization (90C27) Structural characterization of families of graphs (05C75) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A multi-KP modeling for the maximum-clique problem, Solving the maximum clique problem using a tabu search approach, Solving transportation problems with nonlinear side constraints with tabu search, Diversification strategies in tabu search algorithms for the maximum clique problem, Metaheuristics: A bibliography, Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs, On the Shannon capacity of triangular graphs, Reduction of indefinite quadratic programs to bilinear programs, A branch and bound algorithm for the maximum clique problem, Variable neighborhood search for the maximum clique, Finding all \(k\)-cliques in \(k\)-partite graphs, an application in textile engineering, EPCOT: An efficient procedure for coloring optimally with Tabu Search, TABARIS, Constructing a course schedule by solving a series of assignment type problems, Finding maximum cliques in arbitrary and in special graphs, A fast algorithm for the maximum weight clique problem, The maximum clique problem

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using tabu search techniques for graph coloring
• Algorithms for the maximum satisfiability problem
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• STABULUS: A technique for finding stable sets in large graphs with tabu search
• The tabu search metaheuristic: How we used it
• Future paths for integer programming and links to artificial intelligence
• Finding a Maximum Clique in an Arbitrary Graph
• Determining the number of internal stability of a graph
• Tabu Search—Part I
• Algorithm 457: finding all cliques of an undirected graph