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




Related Items (83)

MP or not MP: that is the questionFour Shorts Stories on Surprising Algorithmic Uses of TreewidthAn improved deterministic parameterized algorithm for cactus vertex deletionSeparate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating SetsImproved Algorithms for Sparse MAX-SAT and MAX-k-CSPImproved Upper Bounds for Partial Vertex CoverComputing optimal Steiner trees in polynomial spaceA Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex DeletionA polynomial-time approximation to a minimum dominating set in a graphFrom matchings to independent setsImproved exact algorithms for mildly sparse instances of MAX SATEnumeration of minimal connected dominating sets for chordal graphsExact algorithms for maximum induced matchingThe Parameterized Complexity of the Rainbow Subgraph ProblemA refined algorithm for maximum independent set in degree-4 graphsExact algorithms for weak Roman dominationSatisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite BasesFast exact algorithm for \(L(2,1)\)-labeling of graphsExact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problemA new upper bound for Max-2-SAT: A graph-theoretic approachFurther improvements for SAT in terms of formula lengthSuper-polynomial approximation branching algorithmsLarge Induced Subgraphs via Triangulations and CMSOImproved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanismAn iterated greedy algorithm for finding the minimum dominating set in graphsAn exact algorithm for maximum independent set in degree-5 graphsExact algorithms for dominating setA Polynomial-Space Exact Algorithm for TSP in Degree-6 GraphsExact and parameterized algorithms for \textsc{Max Internal Spanning Tree}Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex coverA universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in betweenOn independent sets and bicliques in graphsCapacitated domination faster than \(O(2^n)\)Advice complexity of adaptive priority algorithmsAn exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}Sharp separation and applications to exact and parameterized algorithmsImproving \(3N\) circuit complexity lower boundsExact algorithms for edge dominationBreaking the \(2^{n}\)-barrier for irredundance: two lines of attackExact algorithms for maximum weighted independent set on sparse graphs (extended abstract)Bicolored independent sets and bicliquesAn exact exponential time algorithm for counting bipartite cliquesSolving vertex cover in polynomial time on hyperbolic random graphsAn exact exponential-time algorithm for the directed maximum leaf spanning tree problemAn exact algorithm for the maximum leaf spanning tree problemComputing the differential of a graph: hardness, approximability and exact algorithmsEnumerating minimal subset feedback vertex setsA note on the independence number, domination number and related parameters of random binary search trees and random recursive treesExact algorithms for KaylesA refined exact algorithm for edge dominating setSolving the 2-disjoint connected subgraphs problem faster than \(2^n\)Finding large \(k\)-clubs in undirected graphsEfficient algorithms for the \textsc{max~\(k\)-vertex cover problem}Improved algorithms for the general exact satisfiability problemA general reduction theorem with applications to pathwidth and the complexity of Max 2-CSPParameterized algorithms and kernels for rainbow matchingParallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithmsAn improved parameterized algorithm for the \(p\)-cluster vertex deletion problemOn optimal approximability results for computing the strong metric dimensionInclusion/exclusion meets measure and conquerScheduling partially ordered jobs faster than \(2^n\)Algorithms for dominating clique problemsParameterized measure \& conquer for problems with no small kernelsExact algorithms for maximum independent setImproved upper bounds for vertex coverIterative compression and exact algorithmsUnnamed ItemEnumerate and Measure: Improving Parameter Budget ManagementExponential Time Complexity of Weighted Counting of Independent SetsInclusion/Exclusion Branching for Partial Dominating Set and Set SplittingA note on the fine-grained complexity of MIS on regular graphsImproved analysis of highest-degree branching for feedback vertex setFaster graph coloring in polynomial spaceOn the Number of Minimal Separators in GraphsAn order-based algorithm for minimum dominating set with application in graph miningExact algorithms for counting 3-colorings of graphsParameterized Algorithms and Kernels for Rainbow MatchingAuto-G-Computation of Causal Effects on a NetworkModerate exponential-time algorithms for scheduling problemsAn Improved Exact Algorithm for Undirected Feedback Vertex SetAn improved exact algorithm for TSP in graphs of maximum degree 4An improved exact algorithm for undirected feedback vertex setA 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