New genetic algorithm approach for the min-degree constrained minimum spanning tree

详细信息    查看全文

• 作者：Rui Salgueiro^a ; ^{rps@mat.uc.pt} ; Ana de Almeida ; ^a ; ^b ; ^{ana.almeida@iscte.pt} ; Orlando Oliveira^c ; ^{orlando@teor.fis.uc.pt}
• 关键词：Combinatorial optimisation ; Degree-constrained spanning tree ; Genetic algorithm ; Heuristic ; Lower bound
• 刊名：European Journal of Operational Research
• 出版年：2017
• 出版时间：1 May 2017
• 年：2017
• 卷：258
• 期：3
• 页码：877-886
• 全文大小：700 K
• 卷排序：258

文摘

New approach for the Min-degree constrained minimum spanning tree problem. Uses a Genetic Algorithm strategy and proposes new tree vectorial representations. Efficiency improvement for the tree generation heu’ristic insuring feasibility. Tested on ‘classical’ graph instances. Performs very well for the harder instances.