Premium
A branch‐and‐cut algorithm for a bipartite graph construction problem in digital communication systems
Author(s) -
Kabakulak Banu,
Taşkin Z. Caner,
Pusane Ali E.
Publication year - 2020
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21914
Subject(s) - bipartite graph , heuristics , algorithm , computer science , integer programming , binary number , graph , mathematics , theoretical computer science , mathematical optimization , arithmetic
We study a bipartite graph (BG) construction problem that arises in digital communication systems. In a digital communication system, information is sent from one place to another over a noisy communication channel using binary symbols (bits). The original information is encoded by adding redundant bits, which are then used to detect and correct errors that may have been introduced during transmission. Harmful structures, such as small cycles, severely deteriorate the error correction capability of a BG. We introduce an integer programming formulation to generate a BG for a given smallest cycle length. We propose a branch‐and‐cut algorithm for its solution and investigate the structural properties of the problem to derive valid inequalities and variable fixing rules. We also introduce heuristics to obtain feasible solutions for the problem. The computational experiments show that our algorithm can generate BGs without small cycles in an acceptable amount of time for practically relevant dimensions.