Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatoria...Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatorial optimization problem,which is widely applied in communication networks,multimodal transportation networks,and data compression.Some approximation algorithms and heuristics algorithms have been proposed for the problem.Firefly algorithm is a new meta-heuristic algorithm.Because of its simplicity and easy implementation,it has been successfully applied in various fields.However,the basic firefly algorithm is not suitable for discrete problems.To this end,a novel discrete firefly algorithm for the MLST problem is proposed in this paper.A binary operation method to update firefly positions and a local feasible handling method are introduced,which correct unfeasible solutions,eliminate redundant labels,and make the algorithm more suitable for discrete problems.Computational results show that the algorithm has good performance.The algorithm can be extended to solve other discrete optimization problems.展开更多
With the development of Internet, frequent pattern mining has been extendedto more complex patterns like tree mining and graph mining. Such applications arise in complexdomains like bioinformatics, web mining, etc. In...With the development of Internet, frequent pattern mining has been extendedto more complex patterns like tree mining and graph mining. Such applications arise in complexdomains like bioinformatics, web mining, etc. In this paper, we present a novel algorithm, namedChopper, to discover frequent subtrees from ordered labeled trees. An extensive performance studyshows that the newly developed algorithm outperforms TreeMiner V, one of the fastest methodsproposed previously, in mining large databases. At the end of this paper, the potential improvementof Chopper is mentioned.展开更多
基金This work is supported by the National Natural Science Foundation of China under Grant 61772179the Hunan Provincial Natural Science Foundation of China under Grant 2019JJ40005+3 种基金the Science and Technology Plan Project of Hunan Province under Grant 2016TP1020the Double First-Class University Project of Hunan Province under Grant Xiangjiaotong[2018]469the Open Fund Project of Hunan Provincial Key Laboratory of Intelligent Information Processing and Application for Hengyang Normal University under Grant IIPA19K02the Science Foundation of Hengyang Normal University under Grant 19QD13.
文摘Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatorial optimization problem,which is widely applied in communication networks,multimodal transportation networks,and data compression.Some approximation algorithms and heuristics algorithms have been proposed for the problem.Firefly algorithm is a new meta-heuristic algorithm.Because of its simplicity and easy implementation,it has been successfully applied in various fields.However,the basic firefly algorithm is not suitable for discrete problems.To this end,a novel discrete firefly algorithm for the MLST problem is proposed in this paper.A binary operation method to update firefly positions and a local feasible handling method are introduced,which correct unfeasible solutions,eliminate redundant labels,and make the algorithm more suitable for discrete problems.Computational results show that the algorithm has good performance.The algorithm can be extended to solve other discrete optimization problems.
文摘With the development of Internet, frequent pattern mining has been extendedto more complex patterns like tree mining and graph mining. Such applications arise in complexdomains like bioinformatics, web mining, etc. In this paper, we present a novel algorithm, namedChopper, to discover frequent subtrees from ordered labeled trees. An extensive performance studyshows that the newly developed algorithm outperforms TreeMiner V, one of the fastest methodsproposed previously, in mining large databases. At the end of this paper, the potential improvementof Chopper is mentioned.
