In wireless artificial intelligent computing systems, the construction of backbone network, which determines the optimum network for a set of given terminal nodes like users, switches, and concentrators, can be naturally formed as the Steiner tree problem. The Steiner tree problem asks for a minimum edge-weighted tree spanning a given set of terminal vertices from a given graph. As a well-known graph problem, many algorithms have been developed for solving this computationally challenging problem in the past decades. However, existing algorithms typically encounter difficulties for solving large instances, i.e., graphs with a high number of vertices and terminals. In this paper, we present a novel partition-and-merge algorithm for effectively handle large-scale graphs. The algorithm breaks the input network into small subgraphs and then merges the subgraphs in a bottom-up manner. In the merging procedure, partial Steiner trees in the subgraphs are also created and optimized by an efficient local optimization. When the merging procedure ends, the algorithm terminates and reports the final solution for the input graph. We evaluated the algorithm on a wide range of benchmark instances, showing that the algorithm outperforms the best-known algorithms on large instances and competes favorably with them on small or middle-sized instances.

Given an undirected graph, the Maximum Clique Problem (MCP) is to find a largest complete subgraph of the graph. MCP is NP-hard and has found many practical applications. In this paper, we propose a parallel Branch-and-Bound (BnB) algorithm to tackle this NP-hard problem, which carries out multiple bounded searches in parallel. Each search has its upper bound and shares a lower bound with the rest of the searches. The potential benefit of the proposed approach is that an active search terminates as soon as the best lower bound found so far reaches or exceeds its upper bound. We describe the implementation of our highly scalable and efficient parallel MCP algorithm, called PBS, which is based on a state-of-the-art sequential MCP algorithm. The proposed algorithm PBS is evaluated on hard DIMACS and BHOSLIB instances. The results show that PBS achieves a near-linear speedup on most DIMACS instances and a super-linear speedup on most BHOSLIB instances. Finally, we give a detailed analysis that explains the good speedups achieved for the tested instances.