Parameterized Complexity Theory

2006/01/01 by Jörg Flum, Martin Grohe · 36 citations
Computer Science · #Advanced Graph Theory Research #Algorithm #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computer science #Parameterized complexity

paper · doi:10.1007/3-540-29953-x

crossref issued 2006/01/01 · crossref published 2006/01/01 · crossref published-print 2006/01/01 · openalex publication_date 2006/01/01 · crossref created 2006/04/28 · crossref deposited 2019/04/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15 · crossref indexed 2026/07/21

Cited by

• Finding All Leftmost Separators of Size ≤ k
• An Improvement of Reed’s Treewidth Approximation
• K-Core Minimization: A Game Theoretic Approach
• Some lower bounds in parameterized \rm AC⁰
• Representing One Letter Weighted Automata Over the Tropical Semiring
• Fixed-parameter algorithms for DAG Partitioning
• Temporal Routing in Static Networks: The Schedule Completion Problem
• Kernelization Lower Bounds Through Colors and IDs
• Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• From b-Coloring to b^*-Coloring: Large Girth and Parameterized Complexity
• On the synchronization of planar automata
• Betweenness parameterized above tight lower bound
• NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs
• On the Parameterized and Approximation Hardness of Metric Dimension
• Metric Dimension of Bounded Width Graphs
• FPT Algorithms for Domination in Biclique-Free Graphs
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Graph modification of bounded size to minor-closed classes as fast as vertex deletion
• Minor-Closed Graph Classes with Bounded Layered Pathwidth
• Kernelization via Sampling with Applications to Dynamic Graph Streams
• Parameterized approximability of maximizing the spread of influence in networks
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Improved bounds for the sunflower lemma
• Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
• Fast Exact Search in Hamming Space with Multi-Index Hashing
• Stable Marriage with Groups of Similar Agents
• Parameterized Modal Satisfiability
• Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction
• Counting Triangulations and other Crossing-free Structures via Onion Layers
• Complexity of the quorum intersection property of the Federated Byzantine Agreement System
• Parameterized Algorithms for Boxicity
• Dominating set is fixed parameter tractable in claw-free graphs
• 2-satisfiability [wikipedia]
• Michael Langston [wikipedia]
• Sunflower (mathematics) [wikipedia]