A System for Constructing Spanning Trees in Graph Networks that Utilize Integer Linear Programming to Enhance Link Fault Tolerances
Hieu Tran The, Kosuke Fujita, Nattapong Kitsuwan · 2023
In this paper, we formulate to optimize the problem related to network failure using the integer linear programming (ILP) method. We aim to minimize the number of spanning trees needed to protect the network in case of link and/or link-node failure. Compared to the traditional approach of constructing spanning trees using heuristic algorithms, our method has successfully reduced the number of trees required for node or link-node failure protection by up to 50%. Reducing the number of spanning trees saves memory requirements for the network route and simplifies network configuration.