About: Chordal completion

An Entity of Type: software, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org:8891

In graph theory, a branch of mathematics, a chordal completion of a given undirected graph G is a chordal graph, on the same vertex set, that has G 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. 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.

Property Value
dbo:abstract
  • In graph theory, a branch of mathematics, a chordal completion of a given undirected graph G is a chordal graph, on the same vertex set, that has G 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 G. 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. (en)
dbo:wikiPageID
  • 48088710 (xsd:integer)
dbo:wikiPageLength
  • 11146 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1106795052 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
gold:hypernym
rdf:type
rdfs:comment
  • In graph theory, a branch of mathematics, a chordal completion of a given undirected graph G is a chordal graph, on the same vertex set, that has G 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. 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. (en)
rdfs:label
  • Chordal completion (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License