Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing

DOI10.1016/J.TCS.2012.07.001MaRDI QIDQ392033zbMATH OpenOpenAlexFDO

Authors Peter Damaschke

Publication date 13 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.07.001

zbMATH Keywords

enumerationlinear systemgroup testingparameterized algorithmhitting setproblem kernelsparse vector

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Chemistry (general) in thermodynamics and heat transfer (80A50)

Recommendations

• Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
• A note on sparse solutions of sparse linear systems
• Fixed-parameter tractability of error correction in graphical linear systems
• Sparse Approximate Solutions to Linear Systems
• Solving linear equations parameterized by Hamming weight

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Unique “Nonnegative” Solution to an Underdetermined System: From Vectors to Matrices
• A competitive algorithm in searching for many edges in a hypergraph
• A group testing problem for graphs with several defective edges
• A group testing problem for hypergraphs of bounded rank
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• An efficient fixed-parameter algorithm for 3-hitting set
• On sparse solutions of underdetermined linear systems
• On the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations
• Parameterized algorithms for \(d\)-hitting set: the weighted case
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Sparse Approximate Solutions to Linear Systems
• Sparse nonnegative solution of underdetermined linear equations by linear programming
• The union of minimal hitting sets: parameterized combinatorial bounds and counting

Cited in

(4)

• Fixed-parameter tractability of error correction in graphical linear systems
• A note on sparse solutions of sparse linear systems
• Parameterized complexity of sparse linear complementarity problems
• Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing

This page was built for publication: Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392033)