Please use this identifier to cite or link to this item:
Type: Artigo
Title: Randomized approximation scheme for steiner multi cycle in the euclidean plane
Author: Lintzmayer, Carla N.
Miyazawa, Flávio K.
Moura, Phablo F. S.
Xavier, Eduardo C.
Abstract: We propose a randomized approximation scheme for the Euclidean Steiner Multi Cycle problem which runs in quasilinear time. In this problem, we are given a set of n pairs of points (terminals) in the Euclidean plane, and the objective is to find a collection of cycles of minimum cost such that and belong to a same cycle, for each . This problem extends the Steiner Cycle problem in the same way the Steiner Forest extends the Steiner Tree problem. Additionally, it has applications on routing problems with pickup and delivery locations
Subject: Algoritmos de aproximação
Country: Países Baixos
Editor: Elsevier
Rights: Fechado
Identifier DOI: 10.1016/j.tcs.2020.06.022
Date Issue: 2020
Appears in Collections:IC - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
626DF9B0-FA8A.pdf841.61 kBAdobe PDFView/Open

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