DFS tree construction: Algorithms and characterizations

DOI10.1007/3-540-50728-0_37MaRDI QIDQ6199456zbMATH OpenOpenAlexFDO

Authors Ephraim Korach, Zvi Ostfeld

Publication date 28 February 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-50728-0_37

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• On the existence of special depth first search trees
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
• Series - parallel graphs and depth-first search trees
• On the recognition of search trees generated by BFS and DFS
• Recognizing graph search trees

Cites work

• A new distributed depth-first-search algorithm
• An efficient parallel algorithm for shifting the root of a depth first spanning tree
• An Efficient Parallel Biconnectivity Algorithm
• Depth-First Search and Linear Graph Algorithms
• Depth-first search is inherently sequential
• Dividing a Graph into Triconnected Components
• Efficient Planarity Testing
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 1219634 (Why is no real title available?)
• Lectures on matroids
• Series - parallel graphs and depth-first search trees
• The even-path problem for graphs and digraphs

Cited in

(10)

• On the recognition of search trees generated by BFS and DFS
• Recognizing graph search trees
• scientific article; zbMATH DE number 7651152 (Why is no real title available?)
• Graph Search Trees and Their Leaves
• Recognizing LBFS trees of bipartite graphs
• On the leaves of graph search trees
• The partial search order problem
• Graph search trees and the Intermezzo problem
• Partial search orderings for MCS on chordal graphs via clique graph decomposition
• Breadth-first search trees with many or few leaves

This page was built for publication: DFS tree construction: Algorithms and characterizations

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