The Parametrized Complexity of Some Fundamental Problems in Coding Theory
From MaRDI portal
DOI10.1137/S0097539797323571zbMATH Open0943.68079MaRDI QIDQ4943754FDOQ4943754
Authors: Michael R. Fellows, Alexander Vardy, Rodney G. Downey, Geoff Whittle 
Publication date: 19 March 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Linear codes (general theory) (94B05) Decoding (94B35)
Cited In (44)
- Hardness of approximating the minimum distance of a linear code
- Parameterized complexity of even/odd subgraph problems
- On the subgroup distance problem.
- Parameterized complexity of generalized domination problems
- The birth and early years of parameterized complexity
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- On the parameterized complexity of \textsc{Girth} and \textsc{Connectivity} problems on linear matroids
- Algorithms for computing parameters of graph-based extensions of BCH codes
- An exact algorithm for connected red-blue dominating set
- Parameterized Intractability of Even Set and Shortest Vector Problem
- Sort and Search: exact algorithms for generalized domination
- Binary constraint satisfaction problems defined by excluded topological minors
- On the complexity of decision problems for counter machines with applications to coding theory
- And/or-convexity: a graph convexity based on processes and deadlock models
- A formula for multiple classifiers in data mining based on Brandt semigroups
- Solving linear equations parameterized by Hamming weight
- Conjunctive-query containment and constraint satisfaction
- On Multidimensional and Monotone k-SUM
- Induced subgraph isomorphism: are some patterns substantially easier than others?
- Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_{p}\) norms
- Minimum light number of lit-only \(\sigma\)-game on a tree
- Confronting intractability via parameters
- Surfing with Rod
- Detecting monomials with \(k\) distinct variables
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- On the parameterized complexity of vertex cover and edge cover with connectivity constraints
- Covering Vectors by Spaces: Regular Matroids
- Parameterized intractability of even set and shortest vector problem from Gap-ETH
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Parameterized complexity of small weight automorphisms and isomorphisms
- Some Applications of Coding Theory in Computational Complexity
- Blum Static Complexity and Encoding Spaces
- Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_p\) norms
- On the complexity of finding large odd induced subgraphs and odd colorings
- Editing to Eulerian graphs
- On the computational complexity of length- and neighborhood-constrained path problems
- The stable marriage problem: an interdisciplinary review from the physicist's perspective
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Improved kernel results for some FPT problems based on simple observations
- The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
- The general \(\sigma \) all-ones problem for trees
This page was built for publication: The Parametrized Complexity of Some Fundamental Problems in Coding Theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4943754)
