Algorithm 447: Efficient algorithms for graph manipulation

John Hopcroft; Robert Tarjan

doi:10.1145/362248.362272

Algorithm 447: Efficient algorithms for graph manipulation

John Hopcroft, Robert Tarjan

Research output: Contribution to journal › Article › peer-review

850 Scopus citations

Abstract

Efficient algorithms are presented for partitioning a graph into connected components, biconnected components and simple paths. The algorithm for partitioning of a graph into simple paths of iterative and each iteration produces a new path between two vertices already on paths. (The start vertex can be specified dynamically.) If V is the number of vertices and E is the number of edges, each algorithm requires time and space proportional to max (V, E) when executed on a random access computer.

Original language	English (US)
Pages (from-to)	372-378
Number of pages	7
Journal	Communications of the ACM
Volume	16
Issue number	6
DOIs	https://doi.org/10.1145/362248.362272
State	Published - Jun 1 1973
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science

Keywords

analysis of algorithms
graph manipulation
graphs

Access to Document

10.1145/362248.362272

Cite this

@article{e4ef8fe3d23c4e7789605e6d62b2d8f6,

title = "Algorithm 447: Efficient algorithms for graph manipulation",

abstract = "Efficient algorithms are presented for partitioning a graph into connected components, biconnected components and simple paths. The algorithm for partitioning of a graph into simple paths of iterative and each iteration produces a new path between two vertices already on paths. (The start vertex can be specified dynamically.) If V is the number of vertices and E is the number of edges, each algorithm requires time and space proportional to max (V, E) when executed on a random access computer.",

keywords = "analysis of algorithms, graph manipulation, graphs",

author = "John Hopcroft and Robert Tarjan",

year = "1973",

month = jun,

day = "1",

doi = "10.1145/362248.362272",

language = "English (US)",

volume = "16",

pages = "372--378",

journal = "Communications of the ACM",

issn = "0001-0782",

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

number = "6",

}

TY - JOUR

T1 - Algorithm 447

T2 - Efficient algorithms for graph manipulation

AU - Hopcroft, John

AU - Tarjan, Robert

PY - 1973/6/1

Y1 - 1973/6/1

N2 - Efficient algorithms are presented for partitioning a graph into connected components, biconnected components and simple paths. The algorithm for partitioning of a graph into simple paths of iterative and each iteration produces a new path between two vertices already on paths. (The start vertex can be specified dynamically.) If V is the number of vertices and E is the number of edges, each algorithm requires time and space proportional to max (V, E) when executed on a random access computer.

AB - Efficient algorithms are presented for partitioning a graph into connected components, biconnected components and simple paths. The algorithm for partitioning of a graph into simple paths of iterative and each iteration produces a new path between two vertices already on paths. (The start vertex can be specified dynamically.) If V is the number of vertices and E is the number of edges, each algorithm requires time and space proportional to max (V, E) when executed on a random access computer.

KW - analysis of algorithms

KW - graph manipulation

KW - graphs

UR - https://www.scopus.com/pages/publications/84976669902

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

U2 - 10.1145/362248.362272

DO - 10.1145/362248.362272

M3 - Article

AN - SCOPUS:84976669902

SN - 0001-0782

VL - 16

SP - 372

EP - 378

JO - Communications of the ACM

JF - Communications of the ACM

IS - 6

ER -

Algorithm 447: Efficient algorithms for graph manipulation

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this