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

      0 references
      0 references
      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
      [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

      Identifiers

      0 references
      0 references
      0 references
      0 references