A linear-time algorithm for finding all feedback vertices

DOI10.1016/0020-0190(78)90015-7MaRDI QIDQ1250830zbMATH OpenOpenAlexFDO

Authors M. R. Garey, Robert E. Tarjan

Publication date 1978

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(78)90015-7

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to combinatorics (05-04) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cites work

• Depth-First Search and Linear Graph Algorithms
• Finding Dominators in Directed Graphs
• scientific article; zbMATH DE number 3550181 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• On the computational power of pushdown automata

Cited in

(4)

• Efficient parallel algorithms for path problems in directed graphs
• Deriving fold/unfold transformations of logic programs using extended OLDT-based abstract interpretation
• On the graph traversal method for evaluating linear binary-chain programs
• When recursion is better than iteration: a linear-time algorithm for directed acyclicity with few error vertices

This page was built for publication: A linear-time algorithm for finding all feedback vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1250830)