Answers are grounded in this paper and cite their sources.
In multiprocessor systems, reliable multi-path transmission is crucial for ensuring network quality of service. A set of k spanning trees rooted at the same node r in a network is said to be k node-independent spanning trees (k node-ISTs) if for each node v other than r, the k paths from r to v, with one path in each spanning tree, are internally node-disjoint. This paper studies the problem of constructing k node-ISTs with minimal total path weight, which is NP-complete and has significant application value in fault-tolerant routing, load balancing and secure communication. Considering the limitation of existing algorithms that have been proposed on specific network topologies or for the case k = 2 are difficult to extend to the case k≥3 in general networks, we propose a heuristic algorithm that can construct the required min k node-ISTs in polynomial time O(kn3) in any network with n nodes. Experimental simulations indicate that the algorithm can construct high-quality solutions in various random networks and some important specific networks. In addition, this algorithm can effectively meet the practical requirements for fault-tolerance in low-cost and high-connectivity networks.
No takes yet. Share an insight, caveat, or question.
Zhu et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: