TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
Balas-Yu algorithmcomputational comparison of algorithmsexact implicit enumerationheuristicmaximum independent set in a graphrandom graphsSTABULARGETABARISTabu Search
Structural characterization of families of graphs (05C75) Numerical mathematical programming methods (65K05) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Large-scale problems in mathematical programming (90C06) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)
In an arbitrary graph G a subset S of nodes is independent if no two nodes of S are linked by an edge of G; and S is independent in G if and only if it is a clique in the complement \(\bar G\) of G. This gives rise to the difficult problem to find in G an independent set with maximum cardinality. Already several exact procedures for graphs of moderate size are known, especially the Balas-Yu algorithm. In the present paper a further algorithm is developed which is an exact implicit enumeration procedure, which uses bounds on the independence number of a subgraph and which is also applicable to graphs of larger size. To find such bounds Tabu Search (TS) techniques are used, and the general method of TS is described in Table 2. The new algorithm is called TABARIS (Tabu And Branch and Bound Applied Repeatedly for Independent Sets); its general procedure is described in detail in a formalized manner (Table 1) and among other things it contains the solution of the following two problems which imply the above mentioned specializations of TS: (1) Finding a large stable set; (2) covering a large node set with certain cliques. These steps and their algorithms are again stated in a formalized manner by tables and the solution of (1) is accomplished by a heuristic procedure which is called STABULARGE (Table 3). To solve (2) three sequential algorithms are given, which are formulated in Tables 4 and 5. - Computational experiments have been performed on random graphs with 40- 400 nodes and with densities between 0.1 and 0.9; the obtained results by applying TABARIS and the Balas-Yu algorithm both are compared and analyzed (Table 6). Finally TABARIS was applied to random graphs with 450 nodes (density 0.5), to one graph with 500 nodes (density 0.5) and to one graph with 1000 nodes (density 0.7) and the results reported in Table 7.
- STABULUS: A technique for finding stable sets in large graphs with tabu search
- scientific article; zbMATH DE number 956850
- An exact algorithm for the maximum stable set problem
- A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
- Fast local search for the maximum independent set problem
- Algorithm 457: finding all cliques of an undirected graph
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Algorithms for the maximum satisfiability problem
- Determining the number of internal stability of a graph
- Finding a Maximum Clique in an Arbitrary Graph
- Future paths for integer programming and links to artificial intelligence
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3904619 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- STABULUS: A technique for finding stable sets in large graphs with tabu search
- Tabu Search—Part I
- The tabu search metaheuristic: How we used it
- Using tabu search techniques for graph coloring
- Reduction of indefinite quadratic programs to bilinear programs
- STABULUS: A technique for finding stable sets in large graphs with tabu search
- Constructing a course schedule by solving a series of assignment type problems
- A fast algorithm for the maximum weight clique problem
- The maximum clique problem
- A multi-KP modeling for the maximum-clique problem
- TABARIS
- EPCOT: An efficient procedure for coloring optimally with Tabu Search
- 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
- Solving the maximum clique problem using a tabu search approach
- A tabu search procedure based on a random roulette diversification for the weighted maximal planar graph problem
- scientific article; zbMATH DE number 956850 (Why is no real title available?)
- A branch and bound algorithm for the maximum clique problem
- Finding all \(k\)-cliques in \(k\)-partite graphs, an application in textile engineering
- Variable neighborhood search for the maximum clique
- Finding maximum cliques in arbitrary and in special graphs
This page was built for publication: TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q750320)
