On the existence of special depth first search trees

DOI10.1002/JGT.3190190408MaRDI QIDQ4842707zbMATH OpenOpenAlexFDO

Authors Ephraim Korach, Zvi Ostfeld

Publication date 26 January 1997

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.3190190408

zbMATH Keywords

complete characterizationdegree sequencegraph algorithmslinear algorithmminorsNP-completerecognitionspanning tree

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the recursion depth of special tree traversal algorithms
• On depth first search trees in \(m\)-out digraphs
• Bounding the depth of search trees
• On the recognition of search trees generated by BFS and DFS
• scientific article; zbMATH DE number 3881890
• The depth-first search tree structure of \(TK_{\aleph_ 0}\)-free graphs
• On the complexity of searching in trees and partially ordered structures
• Depth-First Search and Kuratowski Subgraphs
• scientific article; zbMATH DE number 5373718

Cites work

• Lectures on matroids

Cited in

(9)

• A characterization of planar graphs by Trémaux orders
• Notes on oriented depth-first search and longest paths
• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
• Series - parallel graphs and depth-first search trees
• On Cotree-Critical and DFS Cotree-Critical Graphs
• The recognition problem of graph search trees
• On the recursion depth of special tree traversal algorithms
• DFS tree construction: Algorithms and characterizations
• On depth first search trees in \(m\)-out digraphs

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: On the existence of special depth first search trees

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