### 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 | |

State | Published - Jun 1 1973 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

### Keywords

- analysis of algorithms
- graph manipulation
- graphs

## Cite this

Hopcroft, J., & Tarjan, R. (1973). Algorithm 447: Efficient algorithms for graph manipulation.

*Communications of the ACM*,*16*(6), 372-378. https://doi.org/10.1145/362248.362272