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

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:	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
標簽:	添加標簽沒有標簽, 成為第一個標記此記錄!

相似書籍

An improved approximation algorithm for the s-t path movement problem
由: Wattana Jindaluang, et al.
出版: (2018)

An improved approximation algorithm for the s-t path movement problem
由: Wattana Jindaluang, et al.
出版: (2018)

An improved approximation algorithm for the s-t path movement problem
由: Jindaluang W., et al.
出版: (2017)

Polynomial-time algorithms for path movement problems on trees and unicyclic graphs
由: Varin Chouvatut, et al.
出版: (2020)

Under-sampling by algorithm with performance guaranteed for class-imbalance problem
由: Wattana Jindaluang, et al.
出版: (2018)

Under-sampling by algorithm with performance guaranteed for class-imbalance problem
由: Wattana Jindaluang, et al.
出版: (2018)

The complexity of the overlay network verification and its related problems
由: Wattana Jindaluang, et al.
出版: (2018)

The complexity of the overlay network verification and its related problems
由: Wattana Jindaluang, et al.
出版: (2018)

Training set size reduction in large dataset problems
由: Varin Chouvatut, et al.
出版: (2018)

Virtual piano with real-time interaction using automatic marker detection
由: Varin Chouvatut, et al.
出版: (2018)

Virtual piano with real-time interaction using automatic marker detection
由: Varin Chouvatut, et al.
出版: (2018)

Efficiency comparisons between k-centers and k-means algorithms
由: Varin Chouvatut, et al.
出版: (2018)

It's elementary, my dear watson: Time-optimal sorting algorithms on a completely overlapping network
由: Sanpawat Kantabutra, et al.
出版: (2018)

A 3-phase threshold algorithm for smartphone-based fall detection
由: Theepop Chaitep, et al.
出版: (2018)

A 3-phase threshold algorithm for smartphone-based fall detection
由: Theepop Chaitep, et al.
出版: (2018)

Brain tumor's approximate correspondence and area with interior holes filled
由: Varin Chouvatut, et al.
出版: (2018)

Brain tumor's approximate correspondence and area with interior holes filled
由: Varin Chouvatut, et al.
出版: (2018)

Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems
由: Srinivasan, Aravind
出版: (2014)

Radiographic image enhancement using hybrid algorithm
由: Varin Chouvatut, et al.
出版: (2018)

The non-uniform Bounded Degree Minimum Diameter Spanning Tree problem with an application in P2P networking
由: Chawachat,J., et al.
出版: (2015)

Time-inconsistent control problems, path-dependent PDEs, and neural network approximation
由: Nguwi, Jiang Yu
出版: (2022)

NC algorithms for minimum sum of diameters clustering
由: Nopadon Juneam, et al.
出版: (2018)

NC algorithms for minimum sum of diameters clustering
由: Nopadon Juneam, et al.
出版: (2018)

Traffic signal management using maximum flow approach for consecutive intersections
由: Apinya Ngaosai, et al.
出版: (2019)

The Complexity of the Infinity Replacement Problem in the Cyber Security Model
由: Supachai Mukdasanit, et al.
出版: (2018)

On the parallel complexity of hierarchical clustering and CC-complete problems
由: Raymond Greenlaw, et al.
出版: (2018)

Training set size reduction in large dataset problems
由: Chouvatut V., et al.
出版: (2017)

Efficiency comparisons between k-centers and k-means algorithms
由: Chouvatut V., et al.
出版: (2017)

Approximation Algorithm for Multi-Product Newsboy Problem with Stochastic Yield
由: Natapat Areerakulkan
出版: (2019)

RANDOMIZED ALGORITHMS FOR LEAST SQUARES AND LOW RANK APPROXIMATION PROBLEMS
由: TENG DAN
出版: (2017)

New approximation algorithms for some dynamic storage allocation problems
由: Li, S.C., et al.
出版: (2013)

Approximation algorithms for the consecutive ones submatrix problem on sparse matrices
由: Tan, J., et al.
出版: (2014)

Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems
由: Srinivasan, Aravind
出版: (2014)

Time-optimal user communication and source reachability algorithms in a two-dimensional grid wireless mobility model
由: Pattama Longani, et al.
出版: (2018)

The graph relabeling problem and its variants
由: Geir Agnarsson, et al.
出版: (2018)

The parallel complexities of the K-medians related problems
由: Sirion Vittayakorn, et al.
出版: (2018)

On cyber attacks and the maximum-weight rooted-subtree problem
由: Geir Agnarsson, et al.
出版: (2018)

Greedy, randomized and approximate dynamic programming algorithms for facility location problems
由: Bertsimas, Dimitris, et al.
出版: (2018)

Improved Parallel Approximation of a Class of Integer Programming Problems
由: Alon, N., et al.
出版: (2014)

A mobility model for studying wireless communication and the complexity of problems in the model
由: Raymond Greenlaw, et al.
出版: (2018)