About: Chordal completion

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Chordal completion Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Software, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FChordal_completion&invfp=IFP_OFF&sas=SAME_AS_OFF

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.

Attributes	Values
rdf:type	software
rdfs:label	Chordal completion (en)
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)
dcterms:subject	Graph theory objects
Wikipage page ID	48088710 (xsd:integer)
Wikipage revision ID	1106795052 (xsd:integer)
Link from a Wikipage to another Wikipage	Approximation algorithm Pathwidth Undirected graph Graph theory objects Symmetric matrix Gaussian elimination Graph bandwidth Graph coloring NP-complete Perfect phylogeny Symmetric matrices Claw-free graph Computers and Intractability Planar separator theorem Treewidth Trivially perfect graph Open problem Adjacency matrix Graph theory Tree-depth Interval graph Chordal graph Cograph Phylogenetic tree Phylogeny Planar graph Sparse matrix Exponential time Maximum clique Parameterized complexity dbr:AT-free_graph
sameAs	Chordal completion Chordal completion Chordal completion
dbp:wikiPageUsesTemplate	dbt:Harvtxt dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description
has 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)
gold:hypernym	Graph
prov:wasDerivedFrom	wikipedia-en:Chordal_completion?oldid=1106795052&ns=0
page length (characters) of wiki page	11146 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Chordal_completion
is Link from a Wikipage to another Wikipage of	Glossary of graph theory Computers and Intractability Treewidth Cograph
is foaf:primaryTopic of	wikipedia-en:Chordal_completion

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 54 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software