The recognition problem of graph search trees

DOI10.1137/20M1313301MaRDI QIDQ4997136zbMATH OpenOpenAlexFDO

Authors Jesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, Martin Strehler

Publication date 28 June 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/20m1313301

zbMATH Keywords

chordal graphsLBFSLDFSMCSMNSsearch tree recognition

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Recommendations

• Graph-Theoretic Concepts in Computer Science
• On the existence of special depth first search trees
• Recognizing breadth-first search trees in linear time
• scientific article; zbMATH DE number 17799
• On the end-vertex problem of graph searches

Cites work

• A new LBFS-based algorithm for cocomparability graph recognition
• A random NC algorithm for depth first search
• A Unified View of Graph Searching
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• Algorithms for weakly triangulated graphs
• Characterising AT-free graphs with BFS
• Depth-First Search and Linear Graph Algorithms
• Depth-first search is inherently sequential
• Distance approximating spanning trees
• Edge-disjoint spanning trees and depth-first search
• Efficient Planarity Testing
• Graph algorithms. Edited by Guy Even. With a foreword by Richard M. Karp
• Influence of the tie-break rule on the end-vertex problem
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Linear time LexDFS on cocomparability graphs
• On computing the diameter of real-world undirected graphs
• On end-vertices of lexicographic breadth first searches
• On the end-vertex problem of graph searches
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
• Recognizing breadth-first search trees in linear time
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Some aspects of perfect elimination orderings in chordal graphs
• The LBFS structure and recognition of interval graphs
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(14)

• Graph approach to solving problems of combinatorial recognition
• On the recognition of search trees generated by BFS and DFS
• Recognizing graph search trees
• A Unified View of Graph Searching
• On the end-vertex problem of graph searches
• Graph-Theoretic Concepts in Computer Science
• Linearizing partial search orders
• Graph Search Trees and Their Leaves
• Recognizing LBFS trees of bipartite graphs
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
• On the leaves of graph search trees
• The partial search order problem
• Graph search trees and the Intermezzo problem
• Recognizing breadth-first search trees in linear time

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: The recognition problem of graph search trees

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