Algorithm 447: Efficient algorithms for graph manipulation

John Hopcroft, Robert Tarjan

Research output: Contribution to journalArticle

560 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 languageEnglish (US)
Pages (from-to)372-378
Number of pages7
JournalCommunications of the ACM
Volume16
Issue number6
DOIs
StatePublished - Jun 1 1973
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • analysis of algorithms
  • graph manipulation
  • graphs

Cite this