Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets

DOI10.1007/978-3-662-47672-7_46zbMath1436.68393OpenAlexW2257807048MaRDI QIDQ3448816

Serge Gaspers, Gregory B. Sorkin

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: http://eprints.lse.ac.uk/65060/1/Gaspers_Sorkin_%20Separate%2C%20Measure%20and%20Conquer.pdf

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational aspects of satisfiability (68R07)

Related Items (6)

Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ On approximability of optimization problems related to red/blue-split graphs ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ A modeling and computational study of the frustration index in signed networks ⋮ A faster polynomial-space algorithm for Max 2-CSP ⋮ $K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• Upper bounds on the bisection width of 3- and 4-regular graphs
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• On two techniques of combining branching and treewidth
• AND/OR search spaces for graphical models
• Pathwidth of cubic graphs and exact algorithms
• A comparison of structural CSP decomposition methods
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• Inclusion/exclusion meets measure and conquer
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• New exact algorithms for the 2-constraint satisfaction problem
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets
• A measure & conquer approach for the analysis of exact algorithms
• Polynomial Space Algorithms for Counting Dominating Sets and the Domatic Number
• Inclusion/Exclusion Meets Measure and Conquer
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets