Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorPiva, Breno-
dc.contributor.authorSouza, Cid Carvalho de-
dc.identifier.citationPIVA, B.; SOUZA, C. C. The minimum stabbing triangulation problem: IP models and computational evaluation. Lecture Notes in Computer Science, v. 7422, 2012. Disponível em: <>. Acesso em: 16 mar. 2016.pt_BR
dc.description.abstractThe minimum stabbing triangulation of a set of points in the plane (mstr) was previously investigated in the literature. The complexity of the mstr remains open and, to our knowledge, no exact algorithm was proposed and no computational results were reported earlier in the literature of the problem. This paper presents integer programming (ip) formulations for the mstr, that allow us to solve it exactly through ip branch-and-bound (b&b) algorithms. Moreover, one of these models is the basis for the development of a sophisticated Lagrangian heuristic for the problem. Computational tests were conducted with two instance classes comparing the performance of the latter algorithm against that of a standard (exact) b&b. The results reveal that the Lagrangian algorithm yielded solutions with minute, and often null, duality gaps for instances with several hundreds of points in small computation times.pt_BR
dc.publisherSpringer Berlin Heidelbergpt_BR
dc.subjectMinimum stabbing triangulationpt_BR
dc.subjectInteger programmingpt_BR
dc.subjectProgramação linear inteirapt_BR
dc.titleThe minimum stabbing triangulation problem: IP models and computational evaluationpt_BR
dc.identifier.license© Springer International Publishing AG - Artigo publicado originalmente em:
Appears in Collections:DCOMP - Artigos de periódicos

Files in This Item:
File Description SizeFormat 
MinimumStabbingTriangulation.pdf158,5 kBAdobe PDFThumbnail

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.