An exact and heuristic approach for the <Emphasis Type="Italic">d</Emphasis>-minimum branch vertices problem |
| |
Authors: | Jorge Moreno Yuri Frota Simone Martins |
| |
Institution: | 1.Institute of Computing,Universidade Federal Fluminense,Rio de Janeiro,Brazil |
| |
Abstract: | Given a connected graph \(G=(V,E)\), the d-Minimum Branch Vertices (d-MBV) problem consists in finding a spanning tree of G with the minimum number of vertices with degree strictly greater than d. We developed a Miller–Tucker–Zemlin based formulation with valid inequalities for this problem. The results obtained for different values of d show the effectiveness of the proposed method, which has solved several instances faster than previous methods. Also, an heuristic is proposed for this problem, that was tested on several instances of the Minimum Branch Vertices problem, which is the d-MBV problem, when \(d = 2\). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|