Classical, prize-collecting and node-weighted Steiner tree problems in graphs
Document TypePhD thesis
Access StatusOpen Access
© 2018 Dr Yahui Sun
Steiner tree problems in graphs, as a group of network optimization problems, are traditionally applied to design minimum-cost physical networks. Recently, with the eruption of big data, more and more applications of network data analysis have been explored using a Steiner tree approach. These newly explored applications present serious challenges to conventional Steiner tree techniques. Hence, more powerful Steiner tree techniques are urgently required to support the further exploration of Steiner tree problems in graphs. In this thesis, I explore three Steiner tree problems in graphs: the classical Steiner Tree Problem in Graphs, the Prize-Collecting Steiner Tree Problem, and the Node-Weighted Steiner Tree Problem. First, I explore the classical Steiner Tree Problem in Graphs. I conduct some theoretical analyses on the currently popular Physarum-inspired algorithms to reveal their potential to compute Steiner trees. Based on these analyses, I propose two Physarum-inspired algorithms to solve the classical Steiner Tree Problem in Graphs. These two algorithms demonstrate a more competitive performance than the Genetic algorithm, Discrete Particle Swarm Optimization algorithm and Shortest Path Heuristic algorithm for both randomly generated benchmark instances and real-world Very-Large-Scale Integration instances. Second, I explore the Prize-Collecting Steiner Tree Problem. I propose a Physarum-inspired algorithm to solve this problem in pharmaceutical networks for drug repositioning. This algorithm manifests a more competitive performance than the widely-used Goemans-Williamson algorithm for this newly explored application, where significant costs and risks of drug development can be avoided by identifying drugs with similar therapeutic effects. In addition, I propose several post-processing techniques and two fast heuristic algorithms to design large and low-cost communication networks. These post-processing techniques improve the previous best known solution of one of the largest existing benchmark instances, while these fast heuristic algorithms successfully challenge some newly generated benchmark instances that are tens of times larger than the largest existing ones. Third, I explore the Node-Weighted Steiner Tree Problem. I propose two Physarum-inspired algorithms to solve this problem for instances with multiple compulsory terminals. These two algorithms evince a more competitive performance than the popular Genetic algorithm and Discrete Particle Swarm Optimization algorithm. Furthermore, I modify two simple reduction tests and a fast heuristic algorithm to identify elements of cancer-related signaling pathways in large protein-protein interaction networks. The identification results provide us a deeper understanding towards two important cancer-related signaling pathways. Ultimately, I propose several sophisticated reduction tests, an exact algorithm and a fast heuristic algorithm for constrained relay node placement in cost-aware wireless sensor networks. This newly explored application enables us to individually quantify the costs of relay nodes and transmission routes in designing wireless sensor networks for the first time. In summary, I explore some new applications for three Steiner tree problems in graphs, and more powerful Steiner tree techniques are developed to support this exploration. This work contributes to the promotion of Steiner tree problems in graphs as an important network optimization approach for network data analysis and communication network design.
KeywordsSteiner tree; network science; network data analysis
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References