An algorithm for testing chordality of graphs

DOI10.1016/0020-0190(75)90043-5MaRDI QIDQ1216324zbMATH OpenOpenAlexFDO

Authors Fanica Gavril

Publication date 1975

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

Full work available at URL https://doi.org/10.1016/0020-0190(75)90043-5

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Numerical linear algebra (65F99) Graph theory (05C99) Algorithms in computer science (68W99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Gaussian elimination is not optimal
• Incidence matrices and interval graphs
• On rigid circuit graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Toward Characterization of Perfect Elimination Digraphs
• Triangulated graphs and the elimination process

Cited in

(4)

• Bayesian networks: the minimal triangulations of a graph
• Recognition of perfect elimination bipartite graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs

This page was built for publication: An algorithm for testing chordality of graphs

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