An Improved Approximation Algorithm for the s-t Path Movement Problem
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 t...
Saved in:
Main Authors: | , , , , |
---|---|
Format: | บทความวารสาร |
Language: | English |
Published: |
Science Faculty of Chiang Mai University
2019
|
Online Access: | http://it.science.cmu.ac.th/ejournal/dl.php?journal_id=7681 http://cmuir.cmu.ac.th/jspui/handle/6653943832/63855 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Chiang Mai University |
Language: | English |
Summary: | 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 . |
---|