Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms

DOI10.1145/1198513.1198515zbMath1321.68558OpenAlexW2014430206MaRDI QIDQ2944526

David Eppstein

Publication date: 2 September 2015

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1198513.1198515

zbMATH Keywords

worst-case analysisbacktrackingquasiconvex programmingDavis-Putnam proceduresmethod of feasible directionsautomated analysis of algorithmsmultivariate recurrences

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Nonconvex programming, global optimization (90C26)

Related Items (19)

A Faster Algorithm for Dominating Set Analyzed by the Potential Method ⋮ Computing optimal Steiner trees in polynomial space ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ Exact algorithms for dominating set ⋮ A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between ⋮ Exact algorithms for edge domination ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ A refined exact algorithm for edge dominating set ⋮ Zero-convex functions, perturbation resilience, and subgradient projections for feasibility-seeking methods ⋮ Inclusion/exclusion meets measure and conquer ⋮ Parameterized algorithms for \(d\)-hitting set: the weighted case ⋮ Exact algorithms for maximum independent set ⋮ Inexact graph matching using a hierarchy of matching processes ⋮ On two techniques of combining branching and treewidth ⋮ On the Number of Minimal Separators in Graphs ⋮ An improved exact algorithm for TSP in graphs of maximum degree 4 ⋮ An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure

This page was built for publication: Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms