Geodesic
Algorithm for finding maximum independent set
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 1 (2014), pp. 79-89

Voir la notice de l'article provenant de la source Math-Net.Ru

The article presents an algorithm MaxIS for finding maximum independent set in an undirected graph. This problem is a so-called NP-complete problem, which means the current lack of algorithms for solving it in polynomial time. The proposed algorithm, though also not being a polynomial one, finds a solution faster than the trivial exhaustive algorithm. Each branch of the search tree built by the algorithm MaxIS corresponds to the unique maximal independent set. Results of a comparison of the proposed algorithm with an Robson algorithm, which is now considered one of the best algorithms for the solution of the above problem, are presented. Testing of algorithms have been conducted on some set of arbitrary graphs with different densities. Bibliogr. 6. Il. 4.
Keywords: extremal graph theory, maximum independent set, branch and bound method. 
@article{VSPUI_2014_1_a8,
     author = {I. V. Olemskoy and O. S. Firyulina},
     title = {Algorithm for finding maximum independent set},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {79--89},
     publisher = {mathdoc},
     number = {1},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2014_1_a8/}
}
TY  - JOUR
AU  - I. V. Olemskoy
AU  - O. S. Firyulina
TI  - Algorithm for finding maximum independent set
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2014
SP  - 79
EP  - 89
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2014_1_a8/
LA  - ru
ID  - VSPUI_2014_1_a8
ER  - 
%0 Journal Article
%A I. V. Olemskoy
%A O. S. Firyulina
%T Algorithm for finding maximum independent set
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2014
%P 79-89
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VSPUI_2014_1_a8/
%G ru
%F VSPUI_2014_1_a8
I. V. Olemskoy; O. S. Firyulina. Algorithm for finding maximum independent set. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 1 (2014), pp. 79-89. http://geodesic.mathdoc.fr/item/VSPUI_2014_1_a8/