A piecewise approach for the analysis of exact algorithms

DOI10.1016/J.TCS.2026.115814MaRDI QIDQ6841385zbMATH OpenFDO

Authors Katie Clinch, Serge Gaspers, Zixu He, Abdallah Saffidine, Tiankuang Zhang

Publication date 20 March 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115814

zbMATH Keywords

\textsf{4-coloring}\textsf{\#3-coloring}\textsf{\#\(c\)-coloring}\textsf{\(c\)-coloring}algorithm analysisexact exponential time algorithmsgraph coloringpiecewise analysis

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• 3-coloring in time
• A faster algorithm for dominating set analyzed by the potential method
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• A measure \& conquer approach for the analysis of exact algorithms
• A piecewise approach for the analysis of exact algorithms
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Branch and recharge: exact algorithms for generalized domination
• Exact algorithms for counting 3-colorings of graphs
• Exact algorithms for finding minimum transversals in rank-3 hypergraphs
• Exact algorithms via monotone local search
• Exact algorithms via multivariate subroutines
• Faster graph coloring in polynomial space
• Graph minors. III. Planar tree-width
• scientific article; zbMATH DE number 47161 (Why is no real title available?)
• scientific article; zbMATH DE number 1830756 (Why is no real title available?)
• Improved Exact Algorithms for Counting 3- and 4-Colorings
• New methods for 3-SAT decision and worst-case analysis
• On two techniques of combining branching and treewidth
• Parameterized algorithms
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets

This page was built for publication: A piecewise approach for the analysis of exact algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6841385)