The Weighted Sparsity Problem: Complexity and Algorithms

DOI10.1137/0406005zbMath0772.65035OpenAlexW1965933856MaRDI QIDQ5285937

S. Thomas McCormick, S. Frank Chang

Publication date: 29 June 1993

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0406005

zbMATH Keywords

computational complexitysparse matricesPolynomial algorithmsNP-hardbipartite matching

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity and performance of numerical algorithms (65Y20)

Related Items (1)

Making sparse matrices sparser: Computational results

This page was built for publication: The Weighted Sparsity Problem: Complexity and Algorithms