×

zbMATH — the first resource for mathematics

Characterization and recognition of partial k-trees. (English) Zbl 0622.05017
Combinatorics, graph theory and computing, Proc. 16th Southeast. Conf., Boca Raton/Fla. 1985, Congr. Numerantium 47, 69-75 (1985).
[For the entire collection see Zbl 0619.00006.]
Our interest in the class of k-trees and their subgraphs is motivated by practical applications in areas such as network reliability, concurrent broadcasting, and complexity of queries in a data base system. Because of their bounded decomposability, partial k-trees are efficiently tractable by dynamic programming type of algorithms. Here, we present some partial results leading to recognition of these graphs through application of a set of confluent reductions (rewriting rules) in a manner more efficient than a general brute force recognition method.

MSC:
05C05 Trees
68R10 Graph theory (including graph drawing) in computer science
Keywords:
partial k-trees