Name
Abstract | ||
|---|---|---|
Vertex and edge connectivity are special cases of mixed connectivity, in which all edges and a specified set of vertices play a similar role. Certificates of k -connectivity for a graph are obtained by removing a subset of its edges, while preserving its connectivity up to k . We unify the previous work on connectivity certificates and extend it to handle mixed connectivity and multigraphs. Our treatment contributes a new insight of the pertinent structures, yielding more general results and simpler proofs. Also, we present the first communicationoptimal distributed algorithm for finding mixed connectivity certificates. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0304-3975(98)00023-1 | european symposium on algorithms |
Keywords | DocType | Volume |
mixed connectivity,connectivity certificates,distributed algorithm,mixed connectivity certificate | Journal | 203 |
Issue | ISSN | Citations |
2 | Theoretical Computer Science | 7 |
PageRank | References | Authors |
0.75 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| shimon even | 1 | 2873 | 981.78 |
| Gene Itkis | 2 | 646 | 46.99 |
| Sergio Rajsbaum | 3 | 1367 | 115.89 |