The Parametrized Complexity of Some Fundamental Problems in Coding Theory
From MaRDI portal
Publication:4943754
DOI10.1137/S0097539797323571zbMath0943.68079MaRDI QIDQ4943754
Alexander Vardy, Michael R. Fellows, Geoffrey P. Whittle, Rodney G. Downey
Publication date: 19 March 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Linear codes (general theory) (94B05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Decoding (94B35)
Related Items (34)
The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions. ⋮ On the Parameterized Complexity of Girth and Connectivity Problems on Linear Matroids ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ Solving linear equations parameterized by Hamming weight ⋮ And/or-convexity: a graph convexity based on processes and deadlock models ⋮ The Birth and Early Years of Parameterized Complexity ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\) ⋮ Induced subgraph isomorphism: are some patterns substantially easier than others? ⋮ Editing to Eulerian graphs ⋮ Parameterized complexity of generalized domination problems ⋮ Parameterized complexity of even/odd subgraph problems ⋮ An exact algorithm for connected red-blue dominating set ⋮ Surfing with Rod ⋮ Confronting intractability via parameters ⋮ Detecting monomials with \(k\) distinct variables ⋮ On the parameterized complexity of vertex cover and edge cover with connectivity constraints ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ The stable marriage problem: an interdisciplinary review from the physicist's perspective ⋮ The general \(\sigma \) all-ones problem for trees ⋮ Algorithms for computing parameters of graph-based extensions of BCH codes ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles ⋮ Unnamed Item ⋮ Sort and Search: exact algorithms for generalized domination ⋮ Minimum light number of lit-only \(\sigma\)-game on a tree ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ On the computational complexity of length- and neighborhood-constrained path problems ⋮ On the subgroup distance problem. ⋮ A formula for multiple classifiers in data mining based on Brandt semigroups ⋮ FPT is characterized by useful obstruction sets ⋮ Parameterized complexity of small weight automorphisms and isomorphisms ⋮ On Multidimensional and Monotone k-SUM ⋮ Conjunctive-query containment and constraint satisfaction
This page was built for publication: The Parametrized Complexity of Some Fundamental Problems in Coding Theory
