Chordal completion
In graph theory, a branch of mathematics, a chordal completion of a given undirected graph is a chordal graph, on the same vertex set, that has as a subgraph.
A minimal chordal completion is a chordal completion such that any graph formed by removing an edge would no longer be a chordal completion. A minimum chordal completion is a chordal completion with as few edges as possible.

A different type of chordal completion, one that minimizes the size of the maximum clique in the resulting chordal graph, can be used to define the treewidth of . Chordal completions can also be used to characterize several other graph classes including AT-free graphs, claw-free AT-free graphs, and cographs.

The minimum chordal completion was one of twelve computational problems whose complexity was listed as open in the 1979 book "Computers and Intractability".
Applications of chordal completion include modeling the problem of minimizing fill-in when performing Gaussian elimination on sparse symmetric matrices, and reconstructing phylogenetic trees.

Chordal completions of a graph are sometimes called triangulations, but this term is ambiguous even in the context of graph theory, as it can also refer to maximal planar graphs.
Q131476
graph theory
Concept
Q141488
undirected graph
Concept
Q1322892
chordal graph
Concept
Q761631
maximum clique
Concept
Q5067368
treewidth
Concept
Q5129750
claw-free
Concept
Q5141281
cograph
Concept
Q938821
Computers and Intractability
ORG
Q2658
Gaussian elimination
Concept
Q1050404
sparse
Concept
Q339011
symmetric matrices
Concept
Q242125
phylogenetic tree
Concept
Q547823
planar graph
Concept
Q25304222
Chordal completion
UNK
Q25304222
Chordal completion
UNK
1979-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1979
DATE
studies
studies
publication date