Exhaustive Enumeration of Elementary Trapping Sets of an Arbitrary Tanner Graph

Hossein Falsafain, Seyed Rasoul Mousavi

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


An effective branch-and-bound (B&B) algorithm for exhaustively enumerating the elementary trapping sets (ETSs) in an arbitrary given Tanner graph is described. Given a Tanner graph G and a positive integer ν, we introduce a novel 0-1 integer linear programming (ILP) formulation of the NP-hard problem of finding the minimum ω for which there exists an (ω, ν)-ETS in G. The B&B procedure is then based on the LP relaxation of this 0-1 ILP formulation. Our novel 0-1 ILP description of the problem yields a strong (tight) LP relaxation, which allows the search space to be pruned very effectively, as confirmed by experimental results. An obvious advantage of the proposed approach is that it does not require the input Tanner graph to be of a particular form (e.g., variable-regular).
Original languageEnglish
Pages (from-to)1713-1716
Number of pages4
JournalIEEE Communications Letters
Issue number9
Early online date7 Jul 2016
Publication statusPublished - Sept 2016
Externally publishedYes


Dive into the research topics of 'Exhaustive Enumeration of Elementary Trapping Sets of an Arbitrary Tanner Graph'. Together they form a unique fingerprint.

Cite this