Testing graph connectivity

R. Endre Tarjan

doi:10.1145/800119.803897

Testing graph connectivity

R. Endre Tarjan

Research output: Contribution to journal › Conference article › peer-review

19 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(V^1/2E) time to find a maximum set of node-disjoint paths in a graph, and 0(V^2/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(V^5/2E) time, and the edge connectivity of a graph may be tested in 0(V^5/3E) time.

Original language	English (US)
Pages (from-to)	185-193
Number of pages	9
Journal	Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/800119.803897
State	Published - Jan 1 1974
Externally published	Yes
Event	6th Annual ACM Symposium on Theory of Computing, STOC 1974 - Seattle, United States Duration: Apr 30 1974 → May 2 1974

All Science Journal Classification (ASJC) codes

Software

Keywords

Connectivity
Flow
Graph
Matching
Maximum Flow
Network

Access to Document

10.1145/800119.803897

Cite this

@article{1c0bc27f3bf14f45ad2323fc0e60302d,

title = "Testing graph connectivity",

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.",

keywords = "Connectivity, Flow, Graph, Matching, Maximum Flow, Network",

author = "{Endre Tarjan}, R.",

note = "Publisher Copyright: {\textcopyright} Association for Computing Machinery. All rights reserved.; 6th Annual ACM Symposium on Theory of Computing, STOC 1974 ; Conference date: 30-04-1974 Through 02-05-1974",

year = "1974",

month = jan,

day = "1",

doi = "10.1145/800119.803897",

language = "English (US)",

pages = "185--193",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - Testing graph connectivity

AU - Endre Tarjan, R.

PY - 1974/1/1

Y1 - 1974/1/1

N2 - 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.

AB - 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.

KW - Connectivity

KW - Flow

KW - Graph

KW - Matching

KW - Maximum Flow

KW - Network

UR - http://www.scopus.com/inward/record.url?scp=84910515980&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84910515980&partnerID=8YFLogxK

U2 - 10.1145/800119.803897

DO - 10.1145/800119.803897

M3 - Conference article

AN - SCOPUS:84910515980

SN - 0737-8017

SP - 185

EP - 193

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 6th Annual ACM Symposium on Theory of Computing, STOC 1974

Y2 - 30 April 1974 through 2 May 1974

ER -

Testing graph connectivity

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this