Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing

DOI10.1007/978-3-642-28050-4_8zbMath1352.68101MaRDI QIDQ2891340

Peter Damaschke

Publication date: 15 June 2012

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-28050-4_8

Mathematics Subject Classification ID

65F50: Computational methods for sparse matrices

68Q25: Analysis of algorithms and problem complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• A competitive algorithm in searching for many edges in a hypergraph
• Parameterized algorithms for \(d\)-hitting set: the weighted case
• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• A group testing problem for graphs with several defective edges
• A group testing problem for hypergraphs of bounded rank
• On the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations
• A Unique “Nonnegative” Solution to an Underdetermined System: From Vectors to Matrices
• Sparse Approximate Solutions to Linear Systems
• Sparse nonnegative solution of underdetermined linear equations by linear programming