TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
type: Item
instance of: scholarly article
title: TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
zbMATH Open document ID: 0713.90087
DOI: 10.1016/0305-0548(90)90048-C
author: C. Friden
author: Alain Hertz
author: Dominique De Werra
published in: Computers \& Operations Research
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90-08
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C06
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4174697
zbMATH Keywords: maximum independent set in a graph
zbMATH Keywords: computational comparison of algorithms
zbMATH Keywords: Balas-Yu algorithm
zbMATH Keywords: exact implicit enumeration
zbMATH Keywords: Tabu Search
zbMATH Keywords: TABARIS
zbMATH Keywords: heuristic
zbMATH Keywords: STABULARGE
zbMATH Keywords: random graphs
reviewed by: Heinz-Joachim Presia
describes a project that uses: Algorithm 457
MaRDI profile type: Publication
cites work: Q3941433
cites work: Finding a Maximum Clique in an Arbitrary Graph
cites work: Algorithm 457: finding all cliques of an undirected graph
cites work: Q3682509
cites work: Determining the number of internal stability of a graph
cites work: Q3328583
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
cites work: The tabu search metaheuristic: How we used it
cites work: Future paths for integer programming and links to artificial intelligence
cites work: Tabu Search—Part I
cites work: Algorithms for the maximum satisfiability problem
cites work: STABULUS: A technique for finding stable sets in large graphs with tabu search
cites work: Using tabu search techniques for graph coloring
full work available at URL: 0305-0548(90)90048-c
OpenAlex ID: W2048440507
description: scientific article; zbMATH DE number 4174697