Computing the Stopping Distance of a Tanner Graph is NP-hard
K. Murali Krishnan and Priti Shankar
IISc-CSA-TR-2006-13
(December 2006) Available formats: [pdf]
Filed on December 6, 2006
Updated on December 6, 2006
Two decision problems related to the computation of stopping sets in
Tanner graphs are shown to be NP-complete. It follows as a consequence
that there exists no polynomial time algorithm for computing the
stopping distance of a Tanner graph unless P=NP.
Please bookmark this technical report as http://aditya.csa.iisc.ernet.in/TR/2006/13/.Problems ? Contact techrep@csa.iisc.ernet.in
[Updated at 2009-10-22T06:42Z]