On the recognition of search trees generated by BFS and DFS

DOI10.1016/J.TCS.2022.09.018MaRDI QIDQ2087463zbMATH OpenOpenAlexFDO

Authors Robert Scheffler

Publication date 21 October 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.tcs.2022.09.018

zbMATH Keywords

BFSDFSsplit graphsgeneric searchgraph searchessearch tree recognition

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Recognizing graph search trees
• Recognizing LBFS trees of bipartite graphs
• The recognition problem of graph search trees
• DFS tree construction: Algorithms and characterizations
• Recognizing breadth-first search trees in linear time

Cites work

• scientific article; zbMATH DE number 7255738 (Why is no real title available?)
• A general label search to investigate classical graph search algorithms
• A tie-break model for graph search
• Depth-First Search and Linear Graph Algorithms
• Edge-disjoint spanning trees and depth-first search
• Efficient Planarity Testing
• Graph-theoretic concepts in computer science. 48th international workshop, WG 2022, Tübingen, Germany, June 22--24, 2022. Revised selected papers
• HAMILTONian circuits in chordal bipartite graphs
• Hamiltonian circuits in interval graph generalizations
• Influence of the tie-break rule on the end-vertex problem
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
• Recognizing breadth-first search trees in linear time
• Recognizing graph search trees
• The recognition problem of graph search trees

Cited in

(5)

• Recognizing LBFS trees of bipartite graphs
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
• On the existence of special depth first search trees
• DFS tree construction: Algorithms and characterizations
• Graph Search Trees and Their Leaves

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: On the recognition of search trees generated by BFS and DFS

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