<abstract xml:lang="en" xmlns="http://www.w3.org/1999/xhtml">We are formalizing the algorithm for recognizing chordal graphs by lexicographic breadth-first search as presented in [13, Section 3 of Chapter 4, pp. 81-84]. Then we follow with a formalization of another algorithm serving the same end but based on maximum cardinality search as presented by Tarjan and Yannakakis [25].This work is a part of the MSc work of the first author under supervision of the second author. We would like to thank one of the anonymous reviewers for very useful suggestions.</abstract>

We are formalizing the algorithm for recognizing chordal graphs by lexicographic breadth-first search as presented in [13, Section 3 of Chapter 4, pp. 81-84]. Then we follow with a formalization of another algorithm serving the same end but based on maximum cardinality search as presented by Tarjan and Yannakakis [25].This work is a part of the MSc work of the first author under supervision of the second author. We would like to thank one of the anonymous reviewers for very useful suggestions.

Recognizing Chordal Graphs: Lex BFS and MCS1

Formalized Mathematics

Recognizing Chordal Graphs: Lex BFS and MCS

{"article-title":{"content":"Recognizing Chordal Graphs: Lex BFS and MCS","sup":1}}

We are formalizing the algorithm for recognizing chordal graphs by lexicographic breadth-first search as presented in [13, Section 3 of Chapter 4, pp. 81-84]....

Recognizing Chordal Graphs: Lex BFS and MCS¹

Pubblicato online: 13 giu 2008

Pagine: 187 - 206

DOI: https://doi.org/10.2478/v10037-006-0022-z

This content is open access.