Recognizing LBFS trees of bipartite graphs

DOI10.1016/j.ipl.2024.106483zbMATH Open1541.68301WikidataQ128179322 ScholiaQ128179322MaRDI QIDQ6551704

Robert Scheffler

Publication date: 7 June 2024

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

zbMATH Keywords

BFSgraph algorithmssearch treesLBFSgraph searches

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• A new LBFS-based algorithm for cocomparability graph recognition
• Recognizing breadth-first search trees in linear time
• A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
• Almost diameter of a house-hole-free graph in linear time via LexBFS
• LexBFS-orderings and powers of chordal graphs
• A linear algorithm to color \(i\)-triangulated graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• On the recognition of search trees generated by BFS and DFS
• The LBFS Structure and Recognition of Interval Graphs
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• Algorithmic Aspects of Vertex Elimination on Graphs
• The Recognition Problem of Graph Search Trees
• Graph-Theoretic Concepts in Computer Science
• Diameter determination on restricted graph families
• Linearizing partial search orders
• The diameter of AT‐free graphs
• DFS tree construction: Algorithms and characterizations

This page was built for publication: Recognizing LBFS trees of bipartite graphs