article

Free access

Algorithm 447: efficient algorithms for graph manipulation

Authors:

John Hopcroft,

Robert TarjanAuthors Info & Claims

Communications of the ACM, Volume 16, Issue 6

Pages 372 - 378

https://doi.org/10.1145/362248.362272

Published: 01 June 1973 Publication History

PDF eReader

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.

References

[1]

Fisher, G.J. Computer recognition and extraction of planar graphs from the incidence matrix. IEEE Trans. in Orcuit Theory CT-13, (June 1966), 154-163.

Crossref

Google Scholar

[2]

Harary, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.

Google Scholar

[3]

Holt, R., and Reingold, E. On the time required to detect cycles and connectivity in directed graphs. Comput. Sci. TR 70-33, Cornell U. Ithaca, N.Y.

Google Scholar

[4]

Hopcroft, J., and Tarjan, R. Planarity testing in v log v steps, extended abstract. Stanford U. CS 201, Mar. 1971.

Digital Library

Google Scholar

[5]

Lempel, A., Even, S., and Cederbaum, I. An algorithm for planarity testing of graphs. Theory of Graphs: International Symposium: Rome, July 1966. P. Rosenstiehl (Ed.) Gordon and Breach, New York, 1967, pp. 215-232.

Google Scholar

[6]

Paton, K. An algorithm for the blocks and cutnodes of a graph. Comm. ACM 14, 7(July 1971), 428-475.

Digital Library

Google Scholar

[7]

Shirey, R.W. Implementation and analysis of efficient graph planarity testing. Ph.D. diss., Comput. Sci. Dep., U. of Wisconsin, Madison, Wis., 1969.

Digital Library

Google Scholar

Cited By

View all

Dewar SGrasegger G(2025)The number of realisations of a rigid graph in Euclidean and spherical geometriesAlgebraic Combinatorics10.5802/alco.3907:6(1615-1645)Online publication date: 7-Jan-2025
https://doi.org/10.5802/alco.390
Yang TChen YLiang YYang M(2025)Leveraging On-demand Processing to Co-optimize Scalability and Efficiency for Fully-external Graph ComputationACM Transactions on Storage10.1145/370103721:2(1-31)Online publication date: 8-Feb-2025
https://doi.org/10.1145/3701037
Sasabayashi DTsugawa SNakajima STakahashi TTakayanagi YKoike SKatagiri NKatsura MFuruichi AMizukami YNishiyama SKobayashi HYuasa YTsujino NSakuma AOhmuro NSato YTomimoto KOkada NTada MSuga MMaikusa NPlitman EWannan CZalesky AChakravarty MNoguchi KYamasue HMatsumoto KNemoto TTomita HMizuno MKasai KSuzuki M(2025)Increased structural covariance of cortical measures in individuals with an at-risk mental stateProgress in Neuro-Psychopharmacology and Biological Psychiatry10.1016/j.pnpbp.2024.111197136(111197)Online publication date: Jan-2025
https://doi.org/10.1016/j.pnpbp.2024.111197
Show More Cited By

Algorithm 447: efficient algorithms for graph manipulation
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs

Let $\cal C$ be a family of cliques of a graph G=(V,E). Suppose that each clique C of $\cal C$ is associated with an integer r(C)$, where $r(C) \ge 0$. A vertex v r-dominates a clique C of G if $d(v,x) \le r(C)$ for all $x \in C$, where d(v,x) is the ...
A faster FPT algorithm for 3-path vertex cover

The k-path vertex cover problem (k-PVCP) is to find a minimum set of vertices that meets every path of order k in G.The k-PVCP problem is NP-hard for any integer k 2 .We present a FPT algorithm with runtime O * ( 1.8127 s ) for the 3-PVCP problem, where ...
A Characterization of $K_{2,4}$-Minor-Free Graphs

We provide a complete structural characterization of $K_{2,4}$-minor-free graphs. The 3-connected $K_{2,4}$-minor-free graphs consist of nine small graphs on at most eight vertices, together with a family of planar graphs that contains $2n-8$ ...

Comments

Information & Contributors

Information

Published In

Communications of the ACM Volume 16, Issue 6

June 1973

60 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/362248

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1973

Published in CACM Volume 16, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

747
Total Citations
View Citations
7,453
Total Downloads

Downloads (Last 12 months)1,080
Downloads (Last 6 weeks)228

Reflects downloads up to 05 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dewar SGrasegger G(2025)The number of realisations of a rigid graph in Euclidean and spherical geometriesAlgebraic Combinatorics10.5802/alco.3907:6(1615-1645)Online publication date: 7-Jan-2025
https://doi.org/10.5802/alco.390
Yang TChen YLiang YYang M(2025)Leveraging On-demand Processing to Co-optimize Scalability and Efficiency for Fully-external Graph ComputationACM Transactions on Storage10.1145/370103721:2(1-31)Online publication date: 8-Feb-2025
https://doi.org/10.1145/3701037
Sasabayashi DTsugawa SNakajima STakahashi TTakayanagi YKoike SKatagiri NKatsura MFuruichi AMizukami YNishiyama SKobayashi HYuasa YTsujino NSakuma AOhmuro NSato YTomimoto KOkada NTada MSuga MMaikusa NPlitman EWannan CZalesky AChakravarty MNoguchi KYamasue HMatsumoto KNemoto TTomita HMizuno MKasai KSuzuki M(2025)Increased structural covariance of cortical measures in individuals with an at-risk mental stateProgress in Neuro-Psychopharmacology and Biological Psychiatry10.1016/j.pnpbp.2024.111197136(111197)Online publication date: Jan-2025
https://doi.org/10.1016/j.pnpbp.2024.111197
Ghanem RAli IAbpeikar SKasmarik KGarratt M(2025)Optimizing and predicting swarming collective motion performance for coverage problems solvingEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.109522139:PAOnline publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1016/j.engappai.2024.109522
Zaker M(2025)Upper bounds for some graph invariants in terms of blocks and cut-verticesDiscrete Applied Mathematics10.1016/j.dam.2024.11.020362(50-60)Online publication date: Feb-2025
https://doi.org/10.1016/j.dam.2024.11.020
Eryaşar EÖztürk Sözen EBüyükköse Ş(2024)New Formulas and New Bounds for the First and Second Zagreb Indices of PhenylenesKaradeniz Fen Bilimleri Dergisi10.31466/kfbd.136286414:2(468-475)Online publication date: 18-Jun-2024
https://doi.org/10.31466/kfbd.1362864
Cowgill BPrat AValletti T(2024)Political Power and Market PowerSSRN Electronic Journal10.2139/ssrn.5069368Online publication date: 2024
https://doi.org/10.2139/ssrn.5069368
Roy MVentura EWeil P(2024)The central tree property and algorithmic problems on subgroups of free groupsJournal of Group Theory10.1515/jgth-2023-0050Online publication date: 14-Feb-2024
https://doi.org/10.1515/jgth-2023-0050
Zhou YLi JHao JGlover F(2024)Detecting Critical Nodes in Sparse Graphs via “Reduce-Solve-Combine” Memetic SearchINFORMS Journal on Computing10.1287/ijoc.2022.013036:1(39-60)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/ijoc.2022.0130
Norlinder JYang ABlack-Schaffer DWrigstad TErtl MKirsch C(2024)Mutator-Driven Object Placement using Load BarriersProceedings of the 21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3679007.3685060(14-27)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3679007.3685060
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs

A faster FPT algorithm for 3-path vertex cover

A Characterization of $K_{2,4}$-Minor-Free Graphs

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations