Computing the Stopping Distance of a Tanner Graph Is NP-Hard

DOI10.1109/TIT.2007.896864zbMATH Open1323.68302OpenAlexW2115193201MaRDI QIDQ3548264FDOQ3548264

Authors:

Publication date: 21 December 2008

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tit.2007.896864

Recommendations

• Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs
• The intractability of computing the minimum distance of a code
• Some new NP-complete coding problems
• Sur la complexité d'un problème de codage
• Finding minimum stopping and trapping sets: an integer linear programming approach

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decoding (94B35)

Cited In (2)

• Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs
• On the minimum stopping sets of product codes

This page was built for publication: Computing the Stopping Distance of a Tanner Graph Is NP-Hard

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