Improved Algorithms for the Computation of Special Junction Trees

Abstract

Several intractable (e.g. NP-complete) graph problems can be solved efficiently with help of junction trees without large bags. Graph parameters that measure the suitability of a junction tree include the well known notion of Treewidth, and the related notions of Pathwidth and Treecost. In this thesis, exact algorithms to compute the Pathwidth and Treecost of a given graph are studied. We improve upon the current state algorithms using techniques formerly used for exact algorithms for Treewidth. For the techniques, we discuss whether these are suitable for the computation of Pathwidth and/or Treecost. We give both a theoretical analysis of the running time of our algorithms, and present experimental results. Amongst others, these show that one of our algorithms is sufficiently efficient to compute the Pathwidth exactly of graphs with at most 45 vertices. For Treecost we give an algorithm for finding triangulations of optimal cost that uses O(2^(|V| - W(G))) time, with W(G) the size of the maximum clique in G, assuming this maximum clique is known.