Fundamentals of parameterized complexity
From MaRDI portal
Publication:383833
DOI10.1007/978-1-4471-5559-1zbMath1358.68006OpenAlexW2116087731MaRDI QIDQ383833
Michael R. Fellows, Rodney G. Downey
Publication date: 6 December 2013
Published in: Texts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-1-4471-5559-1
Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of algorithms (68W01)
Related Items (only showing first 100 items - show all)
Destroying Bicolored $P_3$s by Deleting Few Edges ⋮ Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ On the Parameterized Complexity of the Expected Coverage Problem ⋮ On Computing the Hamiltonian Index of Graphs ⋮ Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs ⋮ Collaborating with Hans: Some Remaining Wonderments ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ A Retrospective on (Meta) Kernelization ⋮ Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ Parameterized Algorithms for Queue Layouts ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ Uniform Kernelization Complexity of Hitting Forbidden Minors ⋮ Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs ⋮ New Limits to Classical and Quantum Instance Compression ⋮ A New Approach for Contact Graph Representations and Its Applications ⋮ Solving Problems on Graphs of High Rank-Width ⋮ Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes ⋮ On the Parameterized Complexity of Girth and Connectivity Problems on Linear Matroids ⋮ Labelled well-quasi-order for permutation classes ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Pattern Backtracking Algorithm for the Workflow Satisfiability Problem with User-Independent Constraints ⋮ Consensus Patterns (Probably) Has no EPTAS ⋮ Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints ⋮ Structural Parameterizations of the Mixed Chinese Postman Problem ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter ⋮ Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks ⋮ Harary polynomials ⋮ Unnamed Item ⋮ On Directed Steiner Trees with Multiple Roots ⋮ On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ Structured Connectivity Augmentation ⋮ On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ On Compiling Structured CNFs to OBDDs ⋮ Editing to a Planar Graph of Given Degrees ⋮ Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets ⋮ Bivariate Complexity Analysis of Almost Forest Deletion ⋮ A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion ⋮ Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth ⋮ Sum-of-Products with Default Values: Algorithms and Complexity Results ⋮ Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ Small Resolution Proofs for QBF using Dependency Treewidth ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Finding Points in General Position ⋮ Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Fractals for Kernelization Lower Bounds ⋮ Cameo of a Consummate Computabilist ⋮ Unnamed Item ⋮ On the Computational Complexity of Variants of Combinatorial Voter Control in Elections ⋮ Backdoor Sets for CSP. ⋮ Quantified Constraints in Twenty Seventeen ⋮ Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ How to Navigate Through Obstacles ⋮ Reducing CMSO model checking to highly connected graphs ⋮ Matrix Rigidity from the Viewpoint of Parameterized Complexity ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ Dual parameterization of Weighted Coloring ⋮ Parameterized Complexity of Independent Set in H-Free Graphs. ⋮ A Polynomial Kernel for Diamond-Free Editing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized Complexity of the Workflow Satisfiability Problem ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Dominator and Total Dominator Colorings in Graphs ⋮ Bidimensionality and Kernels ⋮ Connecting the dots (with minimum crossings) ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Kernelization of Whitney Switches ⋮ Basic Terminology, Notation and Results ⋮ Parameterized Algorithms for Queue Layouts ⋮ Unnamed Item ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems ⋮ Computable Complex Analysis
This page was built for publication: Fundamentals of parameterized complexity
