Geodesic
Finding all maximal independent sets of an undirected graph
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 1 (2013), pp. 63-69 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

An algorithm of search for all maximal independent sets in an undirected graph is presented. 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, in the worst cases finds a solution faster than the trivial exhaustive algorithm. Comparison of the suggested algorithm with the known Bron–Kerbosch algorithm over a certain set of random generated graphs with different density values is made. Special attention is paid to the comparison over sparse graphs. Bibliogr. 6.
Keywords: maximal independent set, sparse graph, branch and bound method. 
@article{VSPUI_2013_1_a6,
     author = {O. S. Firyulina},
     title = {Finding all maximal independent sets of an undirected graph},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {63--69},
     year = {2013},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2013_1_a6/}
}
TY  - JOUR
AU  - O. S. Firyulina
TI  - Finding all maximal independent sets of an undirected graph
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2013
SP  - 63
EP  - 69
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2013_1_a6/
LA  - ru
ID  - VSPUI_2013_1_a6
ER  - 
%0 Journal Article
%A O. S. Firyulina
%T Finding all maximal independent sets of an undirected graph
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2013
%P 63-69
%N 1
%U http://geodesic.mathdoc.fr/item/VSPUI_2013_1_a6/
%G ru
%F VSPUI_2013_1_a6
O. S. Firyulina. Finding all maximal independent sets of an undirected graph. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 1 (2013), pp. 63-69. http://geodesic.mathdoc.fr/item/VSPUI_2013_1_a6/

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

[2] Olemskoj I. V., “Algoritm vydelenija strukturnyh osobennostej (The algorithm for allocation of structural features)”, Nikolaj Efimovich Kirin, sb. st., eds. V. V. Zhuk, V. F. Kuzjutin, ASSPIN, St. Petersburg, 2003, 224–251

[3] Olemskoj I. V., Metody integrirovanija sistem strukturno razdelennyh differencial'nyh uravnenij (The methods for the integration of systems of structurally separated differential equations), Izd-vo S.-Peterb. un-ta, St. Petersburg, 2009, 180 pp.

[4] Olemskoj I. V., “Modifikacija algoritma vydelenija strukturnyh osobennostej (The modified algorithm for allocation of structural features)”, Vestn. S.-Peterb. un-ta. Ser. 10: Prikladnaja matematika, informatika, processy upravlenija, 2006, no. 2, 55–65

[5] Olemskoj I. V., “Javnyj metod tipa Runge–Kutty pjatogo porjadka (An explicit fifth-order Runge–Kutta method)”, Vychislitel'nye tehnologii, 10:2 (2005), 87–105 | MR

[6] Bron C., Kerbosch J., “Algorithm 457: Finding all cliques of an undirected graph”, Comm. ACM, 16 (1973), 575–577 | Zbl