Abstract = {For more and more applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. This paper gives an overview of several upper bound heuristics that have been proposed and tested for the problem of determining the treewidth of a graph and finding tree decompositions. Each of the heuristics produces tree decompositions whose width may be larger than the optimal width. However, experiments show that in many cases, the heuristics give tree decompositions whose width is close to the exact treewidth of the input graphs.},
Abstract = {The intersection graph of a family of subtrees in an undirected tree is called a subtree graph. A graph is called chordal if every simple circuit with more than three vertices has an edge connecting two non-consecutive vertices. In this paper, we prove that, for a graph G, the following conditions are equivalent: (i) G is a chordal graph; (ii) G is a subtree graph; (iii) G is a proper subtree graph. Consider a chordal graph G. We give an efficient algorithm for constructing a representation of G by a family of subtrees in a tree.},
Journal = {Journal of Combinatorial Theory, Series B},
Owner = {armin},
Timestamp = {2016.06.28}
}
@Article{heggernes2006,
Title = {Minimal triangulations of graphs: A survey },
Author = {Pinar Heggernes},
Year = {2006},
Doi = {http://dx.doi.org/10.1016/j.disc.2005.12.003},
ISSN = {0012-365X},
Note = {Minimal Separation and Minimal Triangulation },
Abstract = {Any given graph can be embedded in a chordal graph by adding edges, and the resulting chordal graph is called a triangulation of the input graph. In this paper we study minimal triangulations, which are the result of adding an inclusion minimal set of edges to produce a triangulation. This topic was first studied from the standpoint of sparse matrices and vertex elimination in graphs. Today we know that minimal triangulations are closely related to minimal separators of the input graph. Since the first papers presenting minimal triangulation algorithms appeared in 1976, several characterizations of minimal triangulations have been proved, and a variety of algorithms exist for computing minimal triangulations of both general and restricted graph classes. This survey presents and ties together these results in a unified modern notation, keeping an emphasis on the algorithms. },
