Geodesic
A parallel algorithm for computing the critical independence number and related sets
Ars Mathematica Contemporanea, Tome 6 (2013) no. 2, pp. 237-245.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

An independent set Ic is a critical independent set if ∣Ic∣ − ∣N(Ic)∣ ≥ ∣J∣ − ∣N(J)∣, for any independent set J. The critical independence number of a graph is the cardinality of a maximum critical independent set. This number is a lower bound for the independence number and can be computed in polynomial-time. The existing algorithm runs in O(n2. 5 √(m/log n)) time for a graph G with n = ∣V(G)∣ vertices and m edges. It is demonstrated here that there is a parallel algorithm using n processors that runs in O(n1. 5 √(m/log n)) time. The new algorithm returns the union of all maximum critical independent sets. The graph induced on this set is a König-Egerváry graph whose components are either isolated vertices or which have perfect matchings.
DOI : 10.26493/1855-3974.165.b8b
Keywords: critical independent set, critical independence number, independence number, matching number, König-Egerváry graph 
@article{10_26493_1855_3974_165_b8b,
     author = {Ermelinda DeLaVi\~na and Craig Eric Larson},
     title = {A parallel algorithm for computing the critical independence number and related sets},
     journal = {Ars Mathematica Contemporanea},
     pages = {237--245},
     publisher = {mathdoc},
     volume = {6},
     number = {2},
     year = {2013},
     doi = {10.26493/1855-3974.165.b8b},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.165.b8b/}
}
TY  - JOUR
AU  - Ermelinda DeLaViña
AU  - Craig Eric Larson
TI  - A parallel algorithm for computing the critical independence number and related sets
JO  - Ars Mathematica Contemporanea
PY  - 2013
SP  - 237
EP  - 245
VL  - 6
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.165.b8b/
DO  - 10.26493/1855-3974.165.b8b
LA  - en
ID  - 10_26493_1855_3974_165_b8b
ER  - 
%0 Journal Article
%A Ermelinda DeLaViña
%A Craig Eric Larson
%T A parallel algorithm for computing the critical independence number and related sets
%J Ars Mathematica Contemporanea
%D 2013
%P 237-245
%V 6
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.165.b8b/
%R 10.26493/1855-3974.165.b8b
%G en
%F 10_26493_1855_3974_165_b8b
Ermelinda DeLaViña; Craig Eric Larson. A parallel algorithm for computing the critical independence number and related sets. Ars Mathematica Contemporanea, Tome 6 (2013) no. 2, pp. 237-245. doi : 10.26493/1855-3974.165.b8b. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.165.b8b/

Cité par Sources :