Geodesic
Algorithm for finding maximum independent set
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 1 (2014), pp. 79-89 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2014},
     number = {1},
     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
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
%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/

[1] Robson J. M., “Algorithms for maximum independent set”, Journal of Algorithms, 7 (1986), 425–440 | DOI | MR | Zbl

[2] Diestel R., Graph Theory, Springer-Verlag, 2005, 312 pp. | MR | Zbl

[3] Moon J. W., Moser L., “On cliques in graphs”, Israel J. Math., 3 (1965), 23–28 | DOI | MR | Zbl

[4] Olemskoy I. V., “The algorithm for allocation of structural features”, Nikolay Efimovich Kirin, sb. st., eds. V. V. Zhuk, V. F. Kuzyutin, ASSPIN, St.-Petersburg, 2003, 224–251

[5] Olemskoy I. V., “The modified algorithm for allocation of structural features”, Vestnik S.-Peterb. un-ta, ser. 10: Prikladnaya matematika, informatika, processy upravleniya, 2006, no. 2, 55–65

[6] Firyulina I. S., “Finding all maximal independent sets of an undirected graph”, Vestnik S.-Peterb. un-ta, ser. 10: Prikladnaya matematika, informatika, processy upravleniya, 2013, no. 1, 63–69