e-Journal Chiang Mai Journal of Science, Faculty of Science, Chiang Mai University
 







1.0
2023CiteScore
 
33rd percentile
Powered by  Scopus












Journal Volumes


Submit your paper
Download Template

  JOURNAL DETAIL



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 
 [a] W.J., [b] J.C., [b] V.C., Fakcharoenphol*[a] J. and [c] S.K., An Improved Approximation Algorithm for the s-t Path Movement Problem, Chiang Mai Journal of Science, 2017; 44(1): 279-286.
SDGs
View:678 Download:213

Search in this journal


Document Search


Author Search

A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

Popular Search






Chiang Mai Journal of Science

Faculty of Science, Chiang Mai University
239 Huaykaew Road, Tumbol Suthep, Amphur Muang, Chiang Mai 50200 THAILAND
Tel: +6653-943-467




Faculty of Science,
Chiang Mai University




EMAIL
cmjs@cmu.ac.th




Copyrights © Since 2021 All Rights Reserved by Chiang Mai Journal of Science