Necessary Edges in k-Chordalisations of Graphs
Necessary Edges in k-Chordalisations of Graphs
复制标题
图的 k 弦化中的必要边
DOI：
--
复制
发表时间：
2003
影响因子：
1
通讯作者：
H. Bodlaender
中科院分区：
文献类型：
--
作者：
H. Bodlaender
图G=(V，E)的k-弦化是指一个图H=(V，F)是通过在G上加边而得到的，使得H是一个最大团大小至多为k的弦图.本文考虑这样一个问题：给定一个图G=(V，E)，G中不相邻的顶点对，将是G的每个k-弦化中的一条边。这样的一对称为树宽k所必需的。一个等价的公式是：可以将哪些边添加到图G中，使得宽度至多为k的G的每个树分解也是所得图G‘的树分解。给出了树宽k需要点对的一些充分条件和充要条件.对于一个固定的k，可以在线性时间内找到给定图G的树宽k的所有必要点对的集合.如果k是输入的一部分，则这个问题是coNP困难的.当使用区间图(因此路径宽度)代替弦图和树宽时，给出了几个类似的结果。
A k-chordalisation of a graph G = (V,E) is a graph H = (V,F) obtained by adding edges to G, such that H is a chordal graph with maximum clique size at most k. This note considers the problem: given a graph G = (V,E) which pairs of vertices, non-adjacent in G, will be an edge in every k-chordalisation of G. Such a pair is called necessary for treewidth k. An equivalent formulation is: which edges can one add to a graph G such that every tree decomposition of G of width at most k is also a tree decomposition of the resulting graph G′. Some sufficient, and some necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth k. For a fixed k, one can find in linear time for a given graph G the set of all necessary pairs for treewidth k. If k is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth.