IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v33y2021i4p1431-1445.html
   My bibliography  Save this article

Exact Algorithms for the Minimum Load Spanning Tree Problem

Author

Listed:
  • 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)

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.

Suggested Citation

  • Xiaojun Zhu & Shaojie Tang, 2021. "Exact Algorithms for the Minimum Load Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1431-1445, October.
    • Handle: RePEc:inm:orijoc:v:33:y:2021:i:4:p:1431-1445
    DOI: 10.1287/ijoc.2020.1011
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2020.1011
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2020.1011?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Xiaojun Zhu & Guihai Chen & Shaojie Tang & Xiaobing Wu & Bing Chen, 2016. "Fast Approximation Algorithm for Maximum Lifetime Aggregation Trees in Wireless Sensor Networks," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 417-431, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Guang Zhu & Hu Liu & Mining Feng, 2018. "An Evolutionary Game-Theoretic Approach for Assessing Privacy Protection in mHealth Systems," IJERPH, MDPI, vol. 15(10), pages 1-27, October.
    2. Zhao Zhang & Wei Liang & Hongmin W. Du & Siwen Liu, 2022. "Constant Approximation for the Lifetime Scheduling Problem of p -Percent Coverage," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2675-2685, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:33:y:2021:i:4:p:1431-1445. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.