Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
type: Item
instance of: scholarly article
title: Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
zbMATH Open document ID: 1358.68127
author: Peter Damaschke
published in: Theoretical Computer Science
publication date: 2014-01-13T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 80A50
zbMATH DE Number: 6244634
zbMATH Keywords: sparse vector
zbMATH Keywords: linear system
zbMATH Keywords: hitting set
zbMATH Keywords: parameterized algorithm
zbMATH Keywords: enumeration
zbMATH Keywords: problem kernel
zbMATH Keywords: group testing
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.07.001
OpenAlex ID: W2131716254
cites work: On the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations
cites work: A competitive algorithm in searching for many edges in a hypergraph
cites work: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
cites work: The union of minimal hitting sets: parameterized combinatorial bounds and counting
cites work: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
cites work: Sparse nonnegative solution of underdetermined linear equations by linear programming
cites work: Parameterized algorithms for \(d\)-hitting set: the weighted case
cites work: A top-down approach to search-trees: Improved algorithmics for 3-hitting set
cites work: Q4198056
cites work: A group testing problem for graphs with several defective edges
cites work: Q3560376
cites work: Sparse Approximate Solutions to Linear Systems
cites work: An efficient fixed-parameter algorithm for 3-hitting set
cites work: A group testing problem for hypergraphs of bounded rank
cites work: A Unique “Nonnegative” Solution to an Underdetermined System: From Vectors to Matrices
DOI: 10.1016/J.TCS.2012.07.001
description: scientific article; zbMATH DE number 6244634