Testing graph connectivity

Research output: Contribution to journalConference article

17 Scopus citations

Abstract

An algorithm proposed by Dinic for finding maximum flows in networks and by Hopcroft and Karp for finding maximum bipartite matchings is applied to graph connectivity problems. It is shown that the algorithm requires 0(V1/2E) time to find a maximum set of node-disjoint paths in a graph, and 0(V2/3E) time to find a maximum set of edge disjoint paths. These bounds are tight. Thus the node connectivity of a graph may be tested in 0(V5/2E) time, and the edge connectivity of a graph may be tested in 0(V5/3E) time.

Original languageEnglish (US)
Pages (from-to)185-193
Number of pages9
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Jan 1 1974
Externally publishedYes
Event6th Annual ACM Symposium on Theory of Computing, STOC 1974 - Seattle, United States
Duration: Apr 30 1974May 2 1974

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Testing graph connectivity'. Together they form a unique fingerprint.

  • Cite this