Fixed-parameter tractability and completeness II: On completeness for W[1]
From MaRDI portal
Publication:673779
Recommendations
Cites work
- scientific article; zbMATH DE number 125608 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 512804 (Why is no real title available?)
- scientific article; zbMATH DE number 512844 (Why is no real title available?)
- scientific article; zbMATH DE number 1142299 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1499087 (Why is no real title available?)
- scientific article; zbMATH DE number 219251 (Why is no real title available?)
- scientific article; zbMATH DE number 806748 (Why is no real title available?)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XX: Wagner's conjecture
- Nondeterminism within $P^ * $
- On the parameterized complexity of short computation and factorization
Cited in
(only showing first 100 items - show all)- On testing monomials in multivariate polynomials
- The l-diversity problem: tractability and approximability
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Compactors for parameterized counting problems
- Parameterized complexity of \(k\)-anonymity: hardness and tractability
- Parameterized complexity of conflict-free matchings and paths
- Few induced disjoint paths for \(H\)-free graphs
- Domino treewidth
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- The multicolored graph realization problem
- Parameterized algorithms for the happy set problem
- Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
- Turbocharging treewidth heuristics
- Improved approximation algorithms for capacitated fault-tolerant \(k\)-center
- Kernelization: new upper and lower bound techniques
- The Parameterized Complexity of Maximality and Minimality Problems
- scientific article; zbMATH DE number 125608 (Why is no real title available?)
- A Retrospective on (Meta) Kernelization
- On computing large temporal (unilateral) connected components
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Detecting fixed patterns in chordal graphs in polynomial time
- Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- Refined memorization for vertex cover
- Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity?
- Maximum disjoint paths on edge-colored graphs: approximability and tractability
- On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
- On the independent set problem in random graphs
- A characterization of trees having a minimum vertex cover which is also a minimum total dominating set
- Open problems around exact algorithms
- Finding a potential community in networks
- The \(k\)-feature set problem is \(W[2]\)-complete
- Computing the number of induced copies of a fixed graph in a bounded degree graph
- A structural/temporal query language for business processes
- On bounded block decomposition problems for under-specified systems of equations
- Parameterized complexity of generalized domination problems
- Parameterized circuit complexity and the \(W\) hierarchy
- Counting vanishing matrix-vector products
- The Impact of Parameterized Complexity to Interdisciplinary Problem Solving
- The birth and early years of parameterized complexity
- Perfect domination and small cycles
- Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
- A basic parameterized complexity primer
- The complexity of dependency detection and discovery in relational databases
- Barrier coverage with non-uniform lengths to minimize aggregate movements
- Evaluation and enumeration problems for regular path queries
- Parameterized complexity of finding regular induced subgraphs
- On the complexity of fixed parameter clique and dominating set
- Envy-free allocations respecting social networks
- The envy-free matching problem with pairwise preferences
- An algorithmic framework for locally constrained homomorphisms
- Distance-\(d\) independent set problems for bipartite and chordal graphs
- Finding disjoint paths in networks with star shared risk link groups
- Parameterized computational complexity of finding small-diameter subgraphs
- The intractability of computing the Hamming distance
- On the efficiency of polynomial time approximation schemes
- On the complexity of finding and counting solution-free sets of integers
- Two decomposition algorithms for solving a minimum weight maximum clique model for the air conflict resolution problem
- Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
- Parameterized complexity in multiple-interval graphs: domination
- An improved fixed-parameter algorithm for vertex cover
- A branch-price-and-cut algorithm for packing cuts in undirected graphs
- Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
- Parameterized complexity of finding subgraphs with hereditary properties.
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Solving large FPT problems on coarse-grained parallel machines
- Improved parameterized algorithms for network query problems
- Cliques with maximum/minimum edge neighborhood and neighborhood density
- Threshold dominating sets and an improved characterization of \(W[2]\)
- The complexity of finding harmless individuals in social networks
- Simple doubly-efficient interactive proof systems for locally-characterizable sets
- Parameterized complexity of independent set reconfiguration problems
- Complexity and kernels for bipartition into degree-bounded induced graphs
- Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
- A Purely Democratic Characterization of W[1]
- Hardness and tractability of the \(\gamma\)-complete subgraph problem
- Fixed-parameter decidability: extending parameterized complexity analysis
- On the 2-club polytope of graphs
- Kernel bounds for disjoint cycles and disjoint paths
- Advice classes of parametrized tractability
- Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms
- Computing the tandem duplication distance is NP-hard
- Before and after vacuity
- On the space and circuit complexity of parameterized problems: classes and completeness
- On generalizations of the shadow independent set problem
- Kernelization of edge perfect code and its variants
- Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs
- On the kernelization of split graph problems
- On the parameterized complexity of multiple-interval graph problems
- Parameterized Complexity Classes under Logical Reductions
- Lower bounds on kernelization
- Applying modular decomposition to parameterized cluster editing problems
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- On computing large temporal (unilateral) connected components
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Parameterized problems complete for nondeterministic FPT time and logarithmic space
- From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability
- Components in time-varying graphs
- Improved approximations for hard optimization problems via problem instance classification
- Stable matching with multilayer approval preferences: approvals can be harder than strict preferences
This page was built for publication: Fixed-parameter tractability and completeness II: On completeness for W[1]
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673779)
