An Algorithm for the All-pair Shortest Path Problem on Circular Trapezoid Graphs
Article Sidebar
Main Article Content
บทคัดย่อ
Article Details
นโยบายการรับบทความ
กองบรรณาธิการวารสารสถาบันเทคโนโลยีไทย-ญี่ปุ่น มีความยินดีรับบทความจากอาจารย์ประจำ และผู้ทรงคุณวุฒิในสาขาวิศวกรรมศาสตร์และเทคโนโลยี ที่เขียนเป็นภาษาไทยหรือภาษาอังกฤษ ซึ่งผลงานวิชาการที่ส่งมาขอตีพิมพ์ต้องไม่เคยเผยแพร่ในสิ่งพิมพ์อื่นใดมาก่อน และต้องไม่อยู่ในระหว่างการพิจารณาของวารสารอื่นที่นำส่ง ดังนั้นผู้สนใจที่จะร่วมเผยแพร่ผลงานและความรู้ที่ศึกษามาสามารถนำส่งบทความได้ที่กองบรรณาธิการเพื่อเสนอต่อคณะกรรมการกลั่นกรองบทความพิจารณาจัดพิมพ์ในวารสารต่อไป ทั้งนี้บทความที่สามารถเผยแพร่ได้ประกอบด้วยบทความวิจัย ผู้สนใจสามารถศึกษาและจัดเตรียมบทความจากคำแนะนำสำหรับผู้เขียนบทความ
การละเมิดลิขสิทธิ์ถือเป็นความรับผิดชอบของผู้ส่งบทความโดยตรง บทความที่ได้รับการตีพิมพ์ต้องผ่านการพิจารณากลั่นกรองคุณภาพจากผู้ทรงคุณวุฒิและได้รับความเห็นชอบจากกองบรรณาธิการ
ข้อความที่ปรากฏภายในบทความของแต่ละบทความที่ตีพิมพ์ในวารสารวิชาการเล่มนี้ เป็น ความคิดเห็นส่วนตัวของผู้เขียนแต่ละท่าน ไม่เกี่ยวข้องกับสถาบันเทคโนโลยีไทย-ญี่ปุ่น และคณาจารย์ท่านอื่น ๆ ในสถาบัน แต่อย่างใด ความรับผิดชอบด้านเนื้อหาและการตรวจร่างบทความแต่ละบทความเป็นของผู้เขียนแต่ละท่าน หากมีความผิดพลาดใด ๆ ผู้เขียนแต่ละท่านจะต้องรับผิดชอบบทความของตนเองแต่ผู้เดียว
กองบรรณาธิการขอสงวนสิทธิ์มิให้นำเนื้อหา ทัศนะ หรือข้อคิดเห็นใด ๆ ของบทความในวารสารสถาบันเทคโนโลยีไทย-ญี่ปุ่น ไปเผยแพร่ก่อนได้รับอนุญาตจากผู้นิพนธ์ อย่างเป็นลายลักษณ์อักษร ผลงานที่ได้รับการตีพิมพ์ถือเป็นลิขสิทธิ์ของวารสารสถาบันเทคโนโลยีไทย-ญี่ปุ่น
ผู้ประสงค์จะส่งบทความเพื่อตีพิมพ์ในวารสารวิชาการ สถาบันเทคโนโลยีไทย-ญี่ปุ่น สามารถส่ง Online ที่ https://www.tci-thaijo.org/index.php/TNIJournal/ โปรดสมัครสมาชิก (Register) โดยกรอกรายละเอียดให้ครบถ้วนหากต้องการสอบถามข้อมูลเพิ่มเติมที่
- กองบรรณาธิการ วารสารสถาบันเทคโนโลยีไทย-ญี่ปุ่น
- ฝ่ายวิจัยและนวัตกรรม สถาบันเทคโนโลยีไทย-ญี่ปุ่น
เลขที่ 1771/1 สถาบันเทคโนโลยีไทย-ญี่ปุ่น ซอยพัฒนาการ 37-39 ถนนพัฒนาการ แขวงสวนหลวง เขตสวนหลวง กรุงเทพมหานคร 10250 ติดต่อกับคุณพิมพ์รต พิพัฒนกุล (02) 763-2752 , คุณจุฑามาศ ประสพสันติ์ (02) 763-2600 Ext. 2402 Fax. (02) 763-2754 หรือ E-mail: JEDT@tni.ac.th
References
E. W. Dijkstra, “A note on two problems in connection with graphs,” Numerische Mathematlk, vol. 1, pp. 269–271, 1959.
M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms,” J. ACM, vol. 34, no. 3, pp. 596–615, Jul. 1987.
R. W. Floyd, “Algorithm 97: Shortest path,” Communications of the ACM, vol. 5, no. 6, pp. 344-348, Jun. 1962.
S. Warshall, “A theorem on boolean matrices,” J. ACM, vol. 9, no.1, pp. 11–12, Jan. 1962.
Y. Kobayashi and R. Sako, “Two disjoint shortest paths problem with non-negative edge length,” Operations Research Letters, vol. 47, no. 1, pp. 66–69, Jan. 2019.
C. Glacet, N. Hanusse, D. Ilcinkas, and C. Johnen, “Disconnected components detection and rooted shortest-path tree maintenance in networks,” J. Parallel and Distributed Computing, vol. 132, pp. 299–309, Oct. 2019.
M. Debski, K. J. Szaniawski and Z. Lonc, “Bundling all shortest paths,” Discrete Applied Mathematics, vol. 277, pp. 82–91, Apr. 2020.
L. Di Puglia Pugliese, D. Ferone, P. Festa, and F. Guerriero, “Shortest path tour problem with time windows,” European Journal of Operational Research, vol. 282, no. 1, pp. 334–344, Apr. 2020.
F. R. Hsu, K. Shan, H. S. Chao, and R. C. Lee, “Some optimal parallel algorithms on interval and circular-arc graphs,” J. Inf. Sci. Eng., vol. 21, no. 3, pp. 627–642, May 2005.
O. H. Ibarra and Q. Zheng, “An optimal shortest path parallel algorithm for permutation graphs,” J. Parallel and Distributed Computing, vol. 24, no. 1, pp. 94–99, Jan. 1995.
S. Mondal, M. Pal, and T. K. Pal, “An optimal algorithm for solving all-pairs shortest paths on trapezoid graphs,” Int. J. Computational Engineering Science, vol. 3, no. 2, pp. 103–116, 2002.
S. C. Barman, S. Mondal, and M. Pal, “An efficient algorithm to find next-to-shortest path on trapezoid graphs,” Advances in Applied Mathematical Analysis, vol. 2, no. 2, pp. 97–107, 2007.
W. L. Lin, “Circular and circle trapezoid graphs,” J. Sci. Eng. Tech., vol. 2, no. 2, pp. 11–17, 2006.
H. Honma, Y. Nakajima, Y. Aoshima, and S. Masuyama, “A lineartime algorithm for constructing a spanning tree on circular trapezoid graphs,” IEICE Trans. Fundamentals, vol. E96-A, no. 6, pp. 1051–1058, Jun. 2013.
D. Chen, D. T. Lee, R. Sridhar, and C. Sekharam, “Solving the all-pair shortest path query on interval and circular-arc graphs,” Networks, vol. 31, no. 4, pp. 249–258, 1998.
T. W. Kao and S. J. Horng, “Optimal algorithms for computing articulation points and some related problems on a circular-arc graph,” Parallel Computing, vol. 21, no. 6, pp. 953–969, Jun. 1995.
R. D. Lou and M. Sarrafzadeh, “Circular permutation graph family with applications,” Discrete Applied Mathematics, vol. 40, no. 3, pp. 433–457, Dec. 1992.
H. Honma, S. Honma, and S. Masuyama, “An optimal parallel algorithm for constructing a spanning tree on circular permutation graphs,” IEICE Transactions on Information and Systems, vol. E92-D, no. 2, pp. 141–148, Feb. 2009.
H. Honma, K. Abe, Y. Nakajima, and S. Masuyama, “Linear time algorithms for finding articulation and hinge vertices of circular permutation graphs,” IEICE Trans. Inf. & Syst., vol. E96-D, no. 3, pp. 419–425, Mar. 2013.
H. Honma, Y. Nakajima, and S. Masuyama, “An algorithm for hinge vertex problem on circular trapezoid graphs,” Journal of Information Processing, vol. 25, pp. 945–948, Dec. 2017.
D. Bera, M. Pal, and T. K. Pal, “An efficient algorithm for finding all hinge vertices on trapezoid graphs,” Theory of Computing Systems, vol. 36, no. 1, pp. 17–27, Feb. 2003.