Computing Multi-source Shortest Path query with Assembly points (MSPA) is a fundamental graph problem. The MSPA problem locates a set of assembly points to minimize the overall distance for transporting objects from different sources to a destination, where we can assemble objects at assembly points to reduce the total cost. We prove that the MSPA problem is NP-hard. The intuitive method for computing the optimal set of assembly points and the corresponding set of paths is by Branch-and-Bound. However, the combination of different assembly points is exponential. By analyzing the structure of the path set based on the proposed distance graph, we find that the used paths can be combined into a tree. Hence, by defining the state of subtrees and the state transition equation, we propose a dynamic programming (DP) algorithm by pruning the redundant computation of subtrees. The experiment shows that the DP algorithm can achieve three orders of magnitude speedup in query processing time compared with the optimized Branch-and-Bound algorithm. Moreover, we reduce the transition candidates of the DP algorithm from the entire vertex set to certain neighbors. Extensive experiments are conducted on different types of real-world networks to demonstrate the performance of our DP algorithm.

Computing directed Minimum Spanning Tree ($DMST$) is a fundamental problem in graph theory. It is applied in a wide spectrum of fields from computer network and communication protocol design to revenue maximization in social networks and syntactic parsing in Natural Language Processing. State-of-the-art solutions are online algorithms that compute $DMST$ for a given graph and a root. For multi-query requirements, the online algorithm is inefficient. To overcome the drawbacks, in this paper, we propose an indexed approach that reuses the computation result to facilitate single and batch queries. We store all the potential edges of $DMST$ in a hierarchical tree in $O\left(n\right)$ space complexity. Furthermore, we answer the $DMST$ query of any root in $O\left(n\right)$ time complexity. Experimental results demonstrate that our approach can achieve a speedup of 2–3 orders of magnitude in query processing compared to the state-of-the-art while consuming O(n) index size.