On the Complexity of finding stopping set size in Tanner Graphs

The problem of determining whether a tanner graph for a linear block code has a stopping set of a given size is shown to be NP-complete.

Saved in:
Bibliographic Details
Main Authors: Murali Krishnan, K., Priti Shankar
Format: Conference Proceeding
Language:English
Subjects:
Automation
Bipartite graph
Computer science
Failure analysis
Iterative algorithms
Iterative decoding
Linear code
NP-complete problem
Parity check codes
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The problem of determining whether a tanner graph for a linear block code has a stopping set of a given size is shown to be NP-complete.
DOI:10.1109/CISS.2006.286453