No label defined (Q3029044)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4016952
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4016952 |
Statements
1986
0 references
algorithm
0 references
NP-completeness
0 references
k-tree
0 references
k-clique
0 references
Partial k-tree
0 references
k- decomposable graphs
0 references
clique-separators
0 references
0.8148422837257385
0 references
0.8087477684020996
0 references
0.8071423172950745
0 references
[For the entire collection see Zbl 0608.00004.] A graph is a k-tree if it is connected, has no subgraph that is a \((k+2)\)-clique and each of its minimal separators is a k-clique. Partial k-tree is a k-tree from which some edges have been deleted. k- decomposable graphs are defined recursively as follows. G is k- decomposable if either it has at most \(k+1\) vertices, or it has a separator S, \(| S| \leq k\), with G-S having connected components \(C_ 1,C_ 2,...,C_ m\), such that each graph \(G_ i=C_ i+\hat S\) (\(\hat S\) is a clique over the vertices of S; edges between \(C_ i\) and \(\hat S\) are those that existed between \(C_ i\) and S in G) is k- decomposable. In a different paper the authors show that partial k-trees are exactly the k-decomposable graphs. In this note the authors briefly indicate how optimization problems on graphs of bounded decomposability could be solved in linear time using (dynamic programming and) their decomposability via clique-separators.
0 references