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.
%0 Journal Article
%1 citeulike:6201678
%A Hopcroft, John
%A Tarjan, Robert
%C New York, NY, USA
%D 1973
%I ACM
%J Commun. ACM
%K 68w01-algorithms-general
%N 6
%P 372--378
%R 10.1145/362248.362272
%T Algorithm 447: efficient algorithms for graph manipulation
%U http://dx.doi.org/10.1145/362248.362272
%V 16
%X 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.
@article{citeulike:6201678,
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.}},
added-at = {2017-06-29T07:13:07.000+0200},
address = {New York, NY, USA},
author = {Hopcroft, John and Tarjan, Robert},
biburl = {https://www.bibsonomy.org/bibtex/26b29ae70b2fcf14253b2fd203f440f62/gdmcbain},
citeulike-article-id = {6201678},
citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=362248.362272},
citeulike-linkout-1 = {http://dx.doi.org/10.1145/362248.362272},
comment = {(private-note)cited in Wikipedia `Connected components (graph theory)' under `Algorithms'},
doi = {10.1145/362248.362272},
interhash = {f6448db8fc900ad748b92c4dffc72320},
intrahash = {6b29ae70b2fcf14253b2fd203f440f62},
issn = {0001-0782},
journal = {Commun. ACM},
keywords = {68w01-algorithms-general},
month = jun,
number = 6,
pages = {372--378},
posted-at = {2011-06-15 02:32:45},
priority = {2},
publisher = {ACM},
timestamp = {2017-06-29T07:13:07.000+0200},
title = {{Algorithm 447: efficient algorithms for graph manipulation}},
url = {http://dx.doi.org/10.1145/362248.362272},
volume = 16,
year = 1973
}