The parallel complexity of the subgraph connectivity problem
- 1 January 1989
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
It is shown that the problem of testing whether a graph G contains a vertex- (edge-) connected induced subgraph of cardinality k is P-complete for any fixed k>or=3. Moreover, it is shown that approximating within a factor c>1/2 the maximum d for which there is a d-vertex-(d-edge-) connected induced subgraph of G is not in NC, unless P=NC. In contrast, it is known that the problem of finding the Tutte (triconnected) components of G is in NC. On the positive side, it is shown by proving extremal-graph results, that the maximum d for which there is a d-edge-connected induced subgraph of G can be approximated in NC within any factor c<1/2 and that the same is true for vertex connectivity for any C<1/4.Keywords
This publication has 8 references indexed in Scilit:
- A new graph triconnectivity algorithm and its parallelizationCombinatorica, 1992
- Parallel tree contraction and its applicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Parallel Algorithms in Graph Theory: Planarity TestingSIAM Journal on Computing, 1982
- k-Blocks and ultrablocks in graphsJournal of Combinatorial Theory, Series B, 1978
- An Algorithm for Determining Whether the Connectivity of a Graph is at LeastkSIAM Journal on Computing, 1975
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969
- How to Draw a GraphProceedings of the London Mathematical Society, 1963