A general method to speed up fixed-parameter-tractable algorithms
From MaRDI portal
Publication:1607033
DOI10.1016/S0020-0190(00)00004-1zbMath1014.68064OpenAlexW1972845596MaRDI QIDQ1607033
Peter Rossmanith, Rolf Niedermeier
Publication date: 25 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(00)00004-1
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Call control with \(k\) rejections ⋮ On the existence of subexponential parameterized algorithms ⋮ Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms ⋮ Improved exact algorithms for MAX-SAT ⋮ Refined memorization for vertex cover ⋮ A Basic Parameterized Complexity Primer ⋮ A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes ⋮ Polynomial kernels for proper interval completion and related problems ⋮ A golden ratio parameterized algorithm for cluster editing ⋮ New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem ⋮ On making directed graphs transitive ⋮ Vertex cover problem parameterized above and below tight bounds ⋮ Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ Graph Motif Problems Parameterized by Dual ⋮ On the generalized multiway cut in trees problem ⋮ A cubic-vertex kernel for flip consensus tree ⋮ New fixed-parameter algorithms for the minimum quartet inconsistency problem ⋮ Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs ⋮ Fixed parameter algorithms for one-sided crossing minimization revisited ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem ⋮ Complexity and parameterized algorithms for cograph editing ⋮ Two fixed-parameter algorithms for vertex covering by paths on trees ⋮ Improved upper bounds for vertex cover ⋮ Applying modular decomposition to parameterized cluster editing problems ⋮ Fixed-parameter algorithms for cluster vertex deletion ⋮ On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems ⋮ Efficiency in exponential time for domination-type problems ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ Fixed-parameter algorithms for Kemeny rankings ⋮ Going weighted: parameterized algorithms for cluster editing ⋮ Going Weighted: Parameterized Algorithms for Cluster Editing ⋮ A refined search tree technique for dominating set on planar graphs ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments ⋮ An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
Cites Work
