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

• المؤلفون الرئيسيون: Wattana Jindaluang, Jakarin Chawachat, Varin Chouvatut, Jittat Fakcharoenpho, Sanpawat Kantabutra
• التنسيق: บทความวารสาร
• اللغة: English
• منشور في: Science Faculty of Chiang Mai University 2019
• الوصول للمادة أونلاين: http://it.science.cmu.ac.th/ejournal/dl.php?journal_id=7681; http://cmuir.cmu.ac.th/jspui/handle/6653943832/63855

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...