Name
Abstract | ||
|---|---|---|
An independent set I-c is a critical independent set if vertical bar I-c vertical bar - vertical bar N(I-c)vertical bar >= vertical bar J vertical bar - vertical bar N(J)vertical bar, 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(n(2.5) root m/log n) time for a graph G with n = vertical bar V(G)vertical bar vertices and m edges. It is demonstrated here that there is a parallel algorithm using n processors that runs in O(n(1.5) root m/log n) time. The new algorithm returns the union of all maximum critical independent sets. The graph induced on this set is a Konig-Egervary graph whose components are either isolated vertices or which have perfect matchings. |
Year | Venue | Keywords |
|---|---|---|
2013 | ARS MATHEMATICA CONTEMPORANEA | Critical independent set,critical independence number,independence number,matching number,Konig-Egervary graph |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Vertex (geometry),Cycle graph,Cardinality,Matching (graph theory),Independent set,Factor-critical graph,Mathematics,Maximal independent set,Complement graph | Journal | 6 |
Issue | ISSN | Citations |
2 | 1855-3966 | 2 |
PageRank | References | Authors |
0.38 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ermelinda Delavina | 1 | 23 | 4.51 |
| Craig E. Larson | 2 | 15 | 4.55 |