Necessary Edges in k-Chordalisations of Graphs |
| |
Authors: | Hans L. Bodlaender |
| |
Affiliation: | (1) Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands |
| |
Abstract: | 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. |
| |
Keywords: | graph algorithms chordal graphs triangulated graphs treewidth interval graphs pathwidth |
本文献已被 SpringerLink 等数据库收录! |
|