Edge-labeled graph (ELG) is an important abstract model of many practical applications, in which each edge is associated with one or more labels. Searching the minimum label spanning tree (MLST) of ELG is an important issue and proved NP-hard. In the last decade, researchers have put forward some algorithms, however, high computational cost and lower searching effectiveness are still the main obstacles, especially for large-size graphs. In this paper, we propose a heuristic to solve the strong generalized MLST problem (SGMLSTP). We decompose the SGMLSTP into two sub-problems, one is to search a sub-graph containing one or more spanning trees with the minimum labels from the original graph, and another is to search a spanning tree from the acquired sub-graph. As the latter sub-problem is already solved effectively, we focus on the former sub-problem and propose a community-based zigzag piloting algorithm: Firstly a weighted label graph is derived from the edge-labeled graph; then the label graph is partitioned and label communities are chosen in combination to form the initial solutions; finally, the zigzag piloting process is applied to make the initial solutions feasible and refined, of which the optimum one has the least labels. Label partition largely reduces the computation cost of searching the initial solutions, the zigzag piloting process help increase searching effectiveness, and experimental results on typical benchmark datasets fully verify this point and show better effectiveness and performance than that of the state-of-the-art algorithms.

The strong generalized minimum label spanning tree problem (SGMLSTP) is to search the minimum label spanning tree (MLST) from an Edgelabeled graph (ELG), in which each edge is associated with one or more labels. SGMLSTP is commonly existed in reality and proven NP-hard. In recent years, researchers have proposed some algorithms; however, high computational costs are still severe obstacle, especially for large size graphs. In this paper, we propose a novel heuristics to solve SGMLSTP. We decompose the problem into two subproblems, one is to search a connected subgraph with minimum labels from the original graph, the other is to search a spanning tree from the subgraph. As the latter sub-problem is solved, we focus on the former sub-problem and propose a community-based zigzag piloting algorithm: Firstly 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 refine the initial solution. Label partition finds the initial solution quickly, the zigzag piloting process improves solution refinement. Experimental results on typical benchmark datasets show better effectiveness and performance of our algorithm than that of the state-of-the-art algorithms.