Parameterized computation and complexity: a new approach dealing with NP-hardness (Q2576825): Difference between revisions

@@ Property / DOI @@
-.1007/s11390-005-0003-7
@@ Property / DOI: 10.1007/s11390-005-0003-7 / rank @@
-Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s11390-005-0003-7
+Normal rank
@@ Property / OpenAlex ID @@
+W1986447712
@@ Property / OpenAlex ID: W1986447712 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4258216
@@ Property / cites work: Q4258216 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4856179
@@ Property / cites work: Q4856179 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4935970
@@ Property / cites work: Q4935970 / rank @@
+Normal rank
@@ Property / cites work @@
+The inapproximability of non-NP-hard optimization problems.
+Normal rank
@@ Property / cites work @@
+Solving large FPT problems on coarse-grained parallel machines
+Normal rank
@@ Property / cites work @@
+The complexity of type inference for higher-order typed lambda calculi
+Normal rank
@@ Property / cites work @@
+Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
+Normal rank
@@ Property / cites work @@
+Q3688439
@@ Property / cites work: Q3688439 / rank @@
+Normal rank
@@ Property / cites work @@
+Matrix multiplication via arithmetic progressions
@@ Property / cites work: Matrix multiplication via arithmetic progressions / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of database queries
@@ Property / cites work: On the complexity of database queries / rank @@
+Normal rank
@@ Property / cites work @@
+Tight lower bounds for certain parameterized NP-hard problems
+Normal rank
@@ Property / cites work @@
+Q4004178
@@ Property / cites work: Q4004178 / rank @@
+Normal rank
@@ Property / cites work @@
+On limited nondeterminism and the complexity of the V-C dimension
+Normal rank
@@ Property / cites work @@
+On the structure of parameterized problems in NP
@@ Property / cites work: On the structure of parameterized problems in NP / rank @@
+Normal rank
@@ Property / cites work @@
+Computer Science Logic
@@ Property / cites work: Computer Science Logic / rank @@
+Normal rank
@@ Property / cites work @@
+Q4736854
@@ Property / cites work: Q4736854 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4263467
@@ Property / cites work: Q4263467 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4474097
@@ Property / cites work: Q4474097 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2747613
@@ Property / cites work: Q2747613 / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex packings: Structural properties and algorithms
+Normal rank
@@ Property / cites work @@
+Vertex Cover: Further Observations and Further Improvements
+Normal rank
@@ Property / cites work @@
+Graph-Theoretic Concepts in Computer Science
@@ Property / cites work: Graph-Theoretic Concepts in Computer Science / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial-time data reduction for dominating set
@@ Property / cites work: Polynomial-time data reduction for dominating set / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithms for maximum independent sets
@@ Property / cites work: Algorithms for maximum independent sets / rank @@
+Normal rank
@@ Property / cites work @@
+Finding a Maximum Independent Set
@@ Property / cites work: Finding a Maximum Independent Set / rank @@
+Normal rank
@@ Property / cites work @@
+Q4414647
@@ Property / cites work: Q4414647 / rank @@
+Normal rank
@@ Property / cites work @@
+A general method to speed up fixed-parameter-tractable algorithms
+Normal rank
@@ Property / cites work @@
+An improved fixed-parameter algorithm for vertex cover
+Normal rank
@@ Property / cites work @@
+Q4506265
@@ Property / cites work: Q4506265 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4251072
@@ Property / cites work: Q4251072 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for NP-complete problems on planar graphs
+Normal rank
@@ Property / cites work @@
+Applications of a Planar Separator Theorem
@@ Property / cites work: Applications of a Planar Separator Theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Mathematical Foundations of Computer Science 2004
@@ Property / cites work: Mathematical Foundations of Computer Science 2004 / rank @@
+Normal rank
@@ Property / cites work @@
+A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
+Normal rank
@@ Property / cites work @@
+Diameter and treewidth in minor-closed graph families
+Normal rank
@@ Property / cites work @@
+Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
+Normal rank
@@ Property / cites work @@
+Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
+Normal rank
@@ Property / cites work @@
+Q4471291
@@ Property / cites work: Q4471291 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4708588
@@ Property / cites work: Q4708588 / rank @@
+Normal rank
@@ Property / cites work @@
+Color-coding
@@ Property / cites work: Color-coding / rank @@
+Normal rank
@@ Property / cites work @@
+Using nondeterminism to design efficient deterministic algorithms
+Normal rank
@@ Property / cites work @@
+An efficient parameterized algorithm for m-set packing
+Normal rank
@@ Property / cites work @@
+Graph-Theoretic Concepts in Computer Science
@@ Property / cites work: Graph-Theoretic Concepts in Computer Science / rank @@
+Normal rank
@@ Property / cites work @@
+Q5710169
@@ Property / cites work: Q5710169 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3684139
@@ Property / cites work: Q3684139 / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. VIII: A Kuratowski theorem for general surfaces
+Normal rank
@@ Property / cites work @@
+Graph minors. XIII: The disjoint paths problem
@@ Property / cites work: Graph minors. XIII: The disjoint paths problem / rank @@
+Normal rank
@@ Property / cites work @@
+Nonconstructive tools for proving polynomial-time decidability
+Normal rank
@@ Property / cites work @@
+Optimization, approximation, and complexity classes
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
+Normal rank
@@ Property / cites work @@
+Q2843923
@@ Property / cites work: Q2843923 / rank @@
+Normal rank
@@ Property / cites work @@
+Genetic Design of Drugs Without Side-Effects
@@ Property / cites work: Genetic Design of Drugs Without Side-Effects / rank @@
+Normal rank
@@ Property / cites work @@
+Fundamentals of Computation Theory
@@ Property / cites work: Fundamentals of Computation Theory / rank @@
+Normal rank
@@ Property / cites work @@
+Linear FPT reductions and computational lower bounds
+Normal rank
@@ Property / cites work @@
+Beyond <i>NP</i>-completeness for problems of bounded width (extended abstract)
+Normal rank
@@ Property / cites work @@
+On the existence of subexponential parameterized algorithms
+Normal rank
@@ Property / cites work @@
+On fixed-parameter tractability and approximability of NP optimization problems
+Normal rank
@@ Property / cites work @@
+Toward a unified approach for the classification of NP-complete optimization problems
+Normal rank
@@ Property / cites work @@
+Non deterministic polynomial optimization problems and their approximations
+Normal rank
@@ Property / cites work @@
+Q4252365
@@ Property / cites work: Q4252365 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation properties of NP minimization classes
+Normal rank
@@ Property / cites work @@
+Proof verification and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+On the efficiency of polynomial time approximation schemes
+Normal rank
@@ Property / cites work @@
+Q4228486
@@ Property / cites work: Q4228486 / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/S11390-005-0003-7
@@ Property / DOI: 10.1007/S11390-005-0003-7 / rank @@
+Normal rank