On the time required to detect cycles and connectivity in graphs

DOI10.1007/BF01706081zbMath0233.05128OpenAlexW1980616081MaRDI QIDQ5641178

Richard C. Holt, Edward M. Reingold

Publication date: 1972

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01706081

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Connectivity (05C40)

Related Items

Some results on the complexity of families of sets, Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs, On the elusiveness of Hamiltonian property, Complete subgraphs are elusive, Further results on the Aanderaa-Rosenberg conjecture, On recognizing graph properties from adjacency matrices

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• A New Method of Checking the Consistency of Precedence Matrices
• An Appraisal of Some Shortest-Path Algorithms