Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorWattana Jindaluangen_US
dc.contributor.authorJakarin Chawachaten_US
dc.contributor.authorVarin Chouvatuten_US
dc.contributor.authorJittat Fakcharoenphoen_US
dc.contributor.authorSanpawat Kantabutraen_US
dc.description.abstractThis paper considers a movement problem that minimizes the maximum movement of pebbles on a graph to form a path from source vertex to destination vertex . The best known algorithm for this problem is a 7-approximation algorithm developed by Berman, Demaine, and Zadimoghaddam in 2011. We refine the analysis of Berman et al. to obtain an -approximation algorithm for any constant . This problem is a subroutine used by Berman et al. for finding a solution to the connectivity movement problem. Using our improved algorithm as a subroutine, the approximation ratio for the connectivity movement problem improves from 136 to .en_US
dc.publisherScience Faculty of Chiang Mai Universityen_US
dc.titleAn Improved Approximation Algorithm for the s-t Path Movement Problemen_US
article.title.sourcetitleChiang Mai Journal of Scienceen_US
article.volume44en_US of Computer Engineering, Kasetsart University, Bangkok, Thailand.en_US of Computer Science, Chiang Mai University, Chiang Mai, Thailand.en_US of Computer Engineering, Chiang Mai University, Chiang Mai, Thailand.en_US
Appears in Collections:CMUL: Journal Articles

Files in This Item:
There are no files associated with this item.

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