A branch‐and‐cut algorithm for a bipartite graph construction problem in digital communication systems. Issue 2 (6th December 2019)

• Record Type: Journal Article
• Authors: Kabakulak, Banu; Taşkin, Z. Caner; Pusane, Ali E.
• Is Part Of: Networks. Volume 75:Issue 2(2020)
• Page Start: 137
• Page End: 157
• Publication Date: 2019-12-06
• Subjects: bipartite graphs -- branch‐and‐cut algorithm -- integer programming -- symmetry -- telecommunications -- valid inequalities; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21914
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: 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.