A branch-and-cut algorithm for a bipartite graph construction problem in digital communication systems

BaşlıkA branch-and-cut algorithm for a bipartite graph construction problem in digital communication systems
Publication TypeJournal Article
Year of Publication2020
AuthorsKabakulak, B., Z. C. Taşkın, and A. E. Pusane
JournalNetworks
Volume75
Pagination137-157
Anahtar kelimelerbipartite graphs, branch-and-cut algorithm, integer programming, symmetry, telecommunications, valid inequalities
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.

URLhttps://onlinelibrary.wiley.com/doi/abs/10.1002/net.21914
DOI10.1002/net.21914