On the Tree-Degree of Graphs
On the Tree-Degree of Graphs
复制标题
论图的树度
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
H. Müller
中科院分区：
文献类型：
--
作者：
Maw;H. Müller
每个图都是树的子树的边交图。图的树度是指存在子树交模型的树的最小最大度。计算树的度是NP完全的，即使是平面图，但多项式时间算法存在外平面图，无钻石图和弦图。树度有界的图的最小分离子的个数是多项式。这意味着，即使没有预先给出的模型，也可以有效地计算具有有界树度的图的树宽。
Every graph is the edge intersection graph of subtrees of a tree. The tree-degree of a graph is the minimum maximal degree of the underlying tree for which there exists a subtree intersection model. Computing the tree-degree is NP-complete even for planar graphs, but polynomial time algorithms exist for outer-planar graphs, diamond-free graphs and chordal graphs. The number of minimal separators of graphs with bounded tree-degree is polynomial. This implies that the treewidth of graphs with bounded tree-degree can be computed efficiently, even without the model given in advance.