%0 Journal Article %1 Hopcroft1973Algorithm %A Hopcroft, John %A Tarjan, Robert %C New York, NY, USA %D 1973 %I ACM %J Communications of the ACM %K 05c40-connectivity 05c85-graph-algorithms 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{Hopcroft1973Algorithm, 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 = {2019-03-01T00:11:50.000+0100}, address = {New York, NY, USA}, author = {Hopcroft, John and Tarjan, Robert}, biburl = {https://www.bibsonomy.org/bibtex/2a8eca406f64e9e8ca575700c2617c595/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'}, day = 1, doi = {10.1145/362248.362272}, interhash = {f6448db8fc900ad748b92c4dffc72320}, intrahash = {a8eca406f64e9e8ca575700c2617c595}, issn = {00010782}, journal = {Communications of the ACM}, keywords = {05c40-connectivity 05c85-graph-algorithms 68w01-algorithms-general}, month = jun, number = 6, pages = {372--378}, posted-at = {2011-06-15 02:32:45}, priority = {2}, publisher = {ACM}, timestamp = {2019-03-01T00:11:50.000+0100}, title = {{Algorithm 447: efficient algorithms for graph manipulation}}, url = {http://dx.doi.org/10.1145/362248.362272}, volume = 16, year = 1973 }