Exact Algorithms for the Minimum Load Spanning Tree Problem

Xiaojun Zhu () and Shaojie Tang ()
Additional contact information
Xiaojun Zhu: College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
Shaojie Tang: Naveen Jindal School of Management, University of Texas at Dallas, Richardson, Texas 75080

INFORMS Journal on Computing, 2021, vol. 33, issue 4, 1431-1445

Abstract: In a minimum load spanning tree (MLST) problem, we are given an undirected graph and nondecreasing load functions for nodes defined on nodes’ degrees in a spanning tree, and the objective is to find a spanning tree that minimizes the maximum load among all nodes. We propose the first O ∗ ( 2 n ) time exact algorithm for the MLST problem, where n is the number of nodes and O ∗ ignores polynomial factor. The algorithm is obtained by repeatedly querying whether a candidate objective value is feasible, where each query can be formulated as a bounded degree spanning tree problem (BDST). We propose a novel solution to BDST by extending an inclusion-exclusion based algorithm. To further enhance the time efficiency of the previous algorithm, we then propose a faster algorithm by generalizing the concept of branching walks. In addition, for the purpose of comparison, we give the first mixed integer linear programming formulation for MLST. In numerical analysis, we consider various load functions on a randomly generated network. The results verify the effectiveness of the proposed algorithms. Summary of Contribution: Minimum load spanning tree (MLST) plays an important role in various applications such as wireless sensor networks (WSNs). In many applications of WSNs, we often need to collect data from all sensors to some specified sink. In this paper, we propose the first exact algorithms for the MLST problem. Besides having theoretical guarantees, our algorithms have extraordinarily good performance in practice. We believe that our results make significant contributions to the field of graph theory, internet of things, and WSNs.

Keywords: exact algorithm; minimum load spanning tree; wireless sensor networks (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1011 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:4:p:1431-1445

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().