Community-based zigzag piloting algorithm for the strong generalized minimum label spanning tree problem

Abstract

The strong generalized minimum label spanning tree problem (SGMLSTP) is to search the minimum label spanning tree (MLST) from an edge-labeled graph (ELG), in which each edge is associated with one or more labels. The SGMLSTP commonly exists in reality and is proven to be NP-hard. In recent years, researchers have proposed some algorithms; however, because the label coexistence relationship is not properly considered, high computing costs and lower efficiency are still severe obstacles, especially when the graphs are large. In this paper, we rewrite the SGMLSTP model and decompose the problem into two sub-problems: one is to search a connected sub-graph with minimum labels from the original graph, and the other is to search a spanning tree from the sub-graph. As the latter sub-problem is solved, we focus on the former and propose a community-based zigzag piloting algorithm. First, a label graph is derived from the original edge-labeled graph. Then, the label graph is partitioned, and some label community (or community combinations) is chosen to form an initial solution. Finally, the zigzag piloting process is applied to adjust the initial solution. Different from current algorithms that do not consider label coexistence relationships, the proposed algorithm partitions labels and finds the initial solution quickly; the zigzag piloting process improves the solution. Experimental results on typical benchmark datasets show better effectiveness and performance of our algorithm than that of the state-of-the-art algorithms.