### Abstract

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 language | English |
---|---|

Pages (from-to) | 1713-1716 |

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.

## Cite this

Falsafain, H., & Mousavi, S. R. (2016). Exhaustive Enumeration of Elementary Trapping Sets of an Arbitrary Tanner Graph.

*IEEE Communications Letters*,*20*(9), 1713-1716. https://doi.org/10.1109/LCOMM.2016.2587860