Exact Algorithms via Monotone Local Search

DOI10.1145/3284176zbMath1427.68119arXiv1512.01621OpenAlexW2921791163WikidataQ60488372 ScholiaQ60488372MaRDI QIDQ5244381

Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh

Publication date: 21 November 2019

Published in: Journal of the ACM, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.01621

zbMATH Keywords

local searchsatisfiabilityrandomized algorithmsparameterized algorithmsexact exponential algorithmparameterized algorithmsubset problemscombinatorial boundsexponential time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (30)

Enumeration of Maximal Irredundant Sets for Claw-Free Graphs ⋮ Parameterized complexity of \(d\)-hitting set with quotas ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ Simultaneous feedback edge set: a parameterized perspective ⋮ The maximum independent union of cliques problem: complexity and exact approaches ⋮ Improved bounds for minimal feedback vertex sets in tournaments ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs ⋮ Exact algorithms for restricted subset feedback vertex set in chordal and split graphs ⋮ Unnamed Item ⋮ Enumerating Minimal Tropical Connected Sets ⋮ Frameworks for designing in-place graph algorithms ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dynamic parameterized problems ⋮ Vertex deletion problems on chordal graphs ⋮ Faster parameterized algorithm for cluster vertex deletion ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Vertex deletion on split graphs: beyond 4-hitting set ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Subset feedback vertex set in chordal and split graphs ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ Exact algorithms for counting 3-colorings of graphs ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width ⋮ Vertex Deletion Problems on Chordal Graphs

This page was built for publication: Exact Algorithms via Monotone Local Search