A note on lexicographic breadth first search for chordal graphs

DOI10.1016/0020-0190(95)00024-7zbMath0875.68533OpenAlexW2004373890MaRDI QIDQ673001

Klaus Simon

Publication date: 28 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00024-7

zbMATH Keywords

Graph theoryAnalysis of algorithmsCombinatorial problemsChordal graphsClique separators

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Generating and characterizing the perfect elimination orderings of a chordal graph, Bayesian networks: the minimal triangulations of a graph

Cites Work

• Unnamed Item
• On rigid circuit graphs
• Decomposition by clique separators
• Incidence matrices and interval graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs