A measure & conquer approach for the analysis of exact algorithms
From MaRDI portal
Publication:3452221
DOI10.1145/1552285.1552286zbMath1325.68311OpenAlexW2089718638WikidataQ56335609 ScholiaQ56335609MaRDI QIDQ3452221
Fabrizio Grandoni, Fedor V. Fomin, Dieter Kratsch
Publication date: 11 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1552285.1552286
Analysis of algorithms (68W40) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (83)
MP or not MP: that is the question ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ An improved deterministic parameterized algorithm for cactus vertex deletion ⋮ Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP ⋮ Improved Upper Bounds for Partial Vertex Cover ⋮ Computing optimal Steiner trees in polynomial space ⋮ A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ From matchings to independent sets ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ Enumeration of minimal connected dominating sets for chordal graphs ⋮ Exact algorithms for maximum induced matching ⋮ The Parameterized Complexity of the Rainbow Subgraph Problem ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ Exact algorithms for weak Roman domination ⋮ Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases ⋮ Fast exact algorithm for \(L(2,1)\)-labeling of graphs ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ A new upper bound for Max-2-SAT: A graph-theoretic approach ⋮ Further improvements for SAT in terms of formula length ⋮ Super-polynomial approximation branching algorithms ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism ⋮ An iterated greedy algorithm for finding the minimum dominating set in graphs ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ Exact algorithms for dominating set ⋮ A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover ⋮ A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between ⋮ On independent sets and bicliques in graphs ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ Advice complexity of adaptive priority algorithms ⋮ An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set} ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Exact algorithms for edge domination ⋮ Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack ⋮ Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract) ⋮ Bicolored independent sets and bicliques ⋮ An exact exponential time algorithm for counting bipartite cliques ⋮ Solving vertex cover in polynomial time on hyperbolic random graphs ⋮ An exact exponential-time algorithm for the directed maximum leaf spanning tree problem ⋮ An exact algorithm for the maximum leaf spanning tree problem ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ Enumerating minimal subset feedback vertex sets ⋮ A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees ⋮ Exact algorithms for Kayles ⋮ A refined exact algorithm for edge dominating set ⋮ Solving the 2-disjoint connected subgraphs problem faster than \(2^n\) ⋮ Finding large \(k\)-clubs in undirected graphs ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Improved algorithms for the general exact satisfiability problem ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ Parameterized algorithms and kernels for rainbow matching ⋮ Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms ⋮ An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem ⋮ On optimal approximability results for computing the strong metric dimension ⋮ Inclusion/exclusion meets measure and conquer ⋮ Scheduling partially ordered jobs faster than \(2^n\) ⋮ Algorithms for dominating clique problems ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ Exact algorithms for maximum independent set ⋮ Improved upper bounds for vertex cover ⋮ Iterative compression and exact algorithms ⋮ Unnamed Item ⋮ Enumerate and Measure: Improving Parameter Budget Management ⋮ Exponential Time Complexity of Weighted Counting of Independent Sets ⋮ Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting ⋮ A note on the fine-grained complexity of MIS on regular graphs ⋮ Improved analysis of highest-degree branching for feedback vertex set ⋮ Faster graph coloring in polynomial space ⋮ On the Number of Minimal Separators in Graphs ⋮ An order-based algorithm for minimum dominating set with application in graph mining ⋮ Exact algorithms for counting 3-colorings of graphs ⋮ Parameterized Algorithms and Kernels for Rainbow Matching ⋮ Auto-G-Computation of Causal Effects on a Network ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ An Improved Exact Algorithm for Undirected Feedback Vertex Set ⋮ An improved exact algorithm for TSP in graphs of maximum degree 4 ⋮ An improved exact algorithm for undirected feedback vertex set ⋮ A fast algorithm for SAT in terms of formula length
This page was built for publication: A measure & conquer approach for the analysis of exact algorithms