Lexicographic Breadth First Search – A Survey

2004/01/01 by Derek G. Corneil · 19 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Graph #Graph Labeling and Dimension Problems #Lexicographical order #Line graph #Mathematics #Outerplanar graph #Theoretical computer science #Voltage graph

paper · doi:10.1007/978-3-540-30559-0_1

published in Lecture Notes in Computer Science, 1-19 (Springer Berlin Heidelberg)

crossref issued 2004/01/01 · crossref published 2004/01/01 · crossref published-print 2004/01/01 · openalex publication_date 2004/01/01 · crossref created 2010/07/02 · crossref deposited 2020/11/19 · crossref indexed 2024/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Citations

• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Distance-hereditary graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Incidence matrices and interval graphs
• Depth-First Search and Linear Graph Algorithms
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing

Cited by

• Lexicographic breadth-first search [wikipedia]