2010/09/01 by Rémy Belmonte, Belmonte, Rémy, Martin Vatshelle +1
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1009.0216
16 pages, 5 figures
arxiv created 2011/07/08 · arxiv updated 2011/07/11
Boolean-width is a recently introduced graph parameter. Many problems are fixed parameter tractable when parametrized by boolean-width, for instance "Minimum Weighted Dominating Set" (MWDS) problem can be solved in O^*(23k) time given a boolean-decomposition of width k, hence for all graph classes where a boolean-decomposition of width O(log n) can be found in polynomial time, MWDS can be solved in polynomial time. We study graph classes having boolean-width O(log n) and problems solvable in O^*(2O(k)), combining these two results to design polynomial algorithms. We show that for trapezoid graphs, circular permutation graphs, convex graphs, Dilworth-k graphs, circular arc graphs and complements of k-degenerate graphs, boolean-decompositions of width O(log n) can be found in polynomial time. We also show that circular k-trapezoid graphs have boolean-width O(log n), and find such a decomposition if a circular k-trapezoid intersection model is given. For many of the graph classes we also prove that they contain graphs of boolean-width Θ(log n). Further we apply the results from \citeboolw2 to give a new polynomial time algorithm solving all vertex partitioning problems introduced by Proskurowski and Telle \citeTP97. This extends previous results by Kratochvíl, Manuel and Miller \citeKMM95 showing that a large subset of the vertex partitioning problems are polynomial solvable on interval graphs.