Abstract
An effective branchandbound (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 01 integer linear programming (ILP) formulation of the NPhard 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 01 ILP formulation. Our novel 01 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., variableregular).
Original language  English 

Pages (fromto)  17131716 
Number of pages  4 
Journal  IEEE Communications Letters 
Volume  20 
Issue number  9 
Early online date  7 Jul 2016 
DOIs  
Publication status  Published  Sep 2016 
Externally published  Yes 
Fingerprint
Dive into the research topics of 'Exhaustive Enumeration of Elementary Trapping Sets of an Arbitrary Tanner Graph'. Together they form a unique fingerprint.Profiles

Seyed Mousavi
 Research Centre for Computational Science and Mathematical Modelling  Associate
 School of Computing, Electronics and Maths  Lecturer in Computer Science
Person: Teaching and Research