An Accelerated Physarum Solver for Network Optimization.

Area of Science:

• Computational mathematics
• Network optimization
• Algorithm analysis

Background:

• Physarum solver is a novel computational paradigm for network optimization.
• Its iterative linear equation solving leads to low computational performance due to high time complexity and extensive iterations.

Purpose of the Study:

• To address the performance limitations of the Physarum solver.
• To develop enhancement strategies for faster and more efficient network optimization.

Main Methods:

• Pruning inactive nodes and edges to reduce graph size and computational complexity.
• Implementing an early termination strategy by defining a transition phase for edges and using depth-first search to find the optimal path from near-optimal paths.

Main Results:

• The proposed enhancements significantly decrease computational complexity.
• Early termination saves iterations while guaranteeing the optimality of the solution.
• Empirical evaluation on various graph types and real-world networks demonstrates improved performance.

Conclusions:

• The enhanced Physarum solver offers a more computationally efficient approach to network optimization.
• Pruning and early termination are effective strategies for accelerating convergence and reducing resource requirements.
• This accelerated method shows promise for tackling complex network problems more effectively.