Chiang Mai Journal of Science

An Improved Approximation Algorithm for the s-t Path Movement Problem

Paper Type	Contributed Paper
Title	An Improved Approximation Algorithm for the s-t Path Movement Problem
Author	Wattana Jindaluang [a], Jakarin Chawachat [b], Varin Chouvatut [b], Jittat Fakcharoenphol*[a] and Sanpawat Kantabutra [c]
Email	jittat@gmail.com
Abstract: This 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 .
Start & End Page	279 - 286
Received Date	2015-03-20
Revised Date
Accepted Date	2015-07-03
Full Text	Download
Keyword	movement problems, approximation algorithm, graph algorithm
Volume	Vol.44 No.1 (JANUARY 2017)
DOI
Citation	Jindaluang W., Chawachat J., Chouvatut V., Fakcharoenphol J. and Kantabutra S., An Improved Approximation Algorithm for the s-t Path Movement Problem, Chiang Mai J. Sci., 2017; 44(1): 279-286.
SDGs
View:598 Download:192