2015/09/25 by Chiel B. Ten Brinke, Brinke, Chiel B. Ten, Frank J. P. van Houten +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Graph Labeling and Dimension Problems #cs.CC #cs.DM
paper · pdf · doi:10.48550/arxiv.1509.07687
arxiv created 2015/09/25 · openalex publication_date 2015/09/25 · arxiv updated 2015/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we give a number of new exact algorithms and heuristics to compute linear boolean decompositions, and experimentally evaluate these algorithms. The experimental evaluation shows that significant improvements can be made with respect to running time without increasing the width of the generated decompositions. We also evaluated dynamic programming algorithms on linear boolean decompositions for several vertex subset problems. This evaluation shows that such algorithms are often much faster (up to several orders of magnitude) compared to theoretical worst case bounds.