Spanning trees with a constraint on the number of leaves. A new formulation

详细信息    查看全文

• 作者：Luis Gouveia^a ; ^{legouveia@fc.ul.pt} ; Luidi Simonetti^b ; ^{luidi@cos.ufrj.br}
• 关键词：Spanning trees ; Max-leaves ; ILP reformulations ; Combinatorial optimization
• 刊名：Computers & Operations Research
• 出版年：2017
• 出版时间：May 2017
• 年：2017
• 卷：81
• 期：Complete
• 页码：257-268
• 全文大小：556 K
• 卷排序：81

文摘

New extended model for finding a minimum cost spanning tree such that the number of leaves is equal to (greater than, less than) k. Model with enhanced cut constraints. New model improves previously known gaps for the three constrained versions and leads to best solution times. For the max-leaves problem the new model proves to be competitive with the existent approaches.