An Iterative Refinement Algorithm for the Minimum Branch Vertices Problem

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2011

Autores

Diego M Silva (Autor) Outra; Ricardo M A Silva (Autor) Outra; Gerald R Mateus (Autor) Outra; Jose F Goncalves (Autor) FEP; Mauricio G C Resende (Autor) Outra; Paola Festa (Autor) Outra

Ata de Conferência Internacional

Título: EXPERIMENTAL ALGORITHMS

Páginas: 421-433

10th International Symposium on Experimental Algorithms

Kolimpari, GREECE, MAY 05-07, 2011

Indexação

ISI Web of Knowledge - 6 Citações

Scopus - 6 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: P-007-YAX

DOI: 10.1007/978-3-642-20662-7_36

Abstract (EN): This paper presents a new approach to solve the NP-complete minimum branch vertices problem (MBV) introduced by Gargano et. al[1]. In spite of being a recently proposed problem in the network optimization literature, there are some heuristics to solve it [3]. The main contribution of this paper consists in a new heuristic based on the iterative refinement approach proposed by Deo and Kumar [2]. The experimental results suggest that this approach is capable of finding solutions that are better than the best known in the literature. In this work, for instance, the proposed heuristic found better solutions for 78% of the instances tested. The heuristic looks very promising for the solution of problems related with constrained spanning trees.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 13