Algorithm for Solving the Detour Hinge Vertex Problem on Circular-arc Graphs
Article Sidebar
Main Article Content
บทคัดย่อ
Consider a simple undirected graph with vertex set
and edge set
. Let
be a subgraph induced by the vertex set
. The distance
is defined as the length of the shortest path between vertices
and
in
. The vertex
is a hinge vertex if there are two vertices
such that
. Let
be a set consisting of all hinge vertices of
. The neighborhood of
, denoted by
, is the set of all vertices adjacent to
. We define the detour degree of
as
for
. The detour hinge vertex problem aims to determine the hinge vertex
that maximizes
in
. In this study, we proposed an efficient algorithm for solving the detour hinge vertex problem on circular-arc graphs that runs in
time, where
is the number of vertices in the graph.
Article Details
อนุญาตภายใต้เงื่อนไข Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
นโยบายการรับบทความ
กองบรรณาธิการวารสารสถาบันเทคโนโลยีไทย-ญี่ปุ่น มีความยินดีรับบทความจากอาจารย์ประจำ และผู้ทรงคุณวุฒิในสาขาวิศวกรรมศาสตร์และเทคโนโลยี ที่เขียนเป็นภาษาไทยหรือภาษาอังกฤษ ซึ่งผลงานวิชาการที่ส่งมาขอตีพิมพ์ต้องไม่เคยเผยแพร่ในสิ่งพิมพ์อื่นใดมาก่อน และต้องไม่อยู่ในระหว่างการพิจารณาของวารสารอื่นที่นำส่ง ดังนั้นผู้สนใจที่จะร่วมเผยแพร่ผลงานและความรู้ที่ศึกษามาสามารถนำส่งบทความได้ที่กองบรรณาธิการเพื่อเสนอต่อคณะกรรมการกลั่นกรองบทความพิจารณาจัดพิมพ์ในวารสารต่อไป ทั้งนี้บทความที่สามารถเผยแพร่ได้ประกอบด้วยบทความวิจัย ผู้สนใจสามารถศึกษาและจัดเตรียมบทความจากคำแนะนำสำหรับผู้เขียนบทความ
การละเมิดลิขสิทธิ์ถือเป็นความรับผิดชอบของผู้ส่งบทความโดยตรง บทความที่ได้รับการตีพิมพ์ต้องผ่านการพิจารณากลั่นกรองคุณภาพจากผู้ทรงคุณวุฒิและได้รับความเห็นชอบจากกองบรรณาธิการ
ข้อความที่ปรากฏภายในบทความของแต่ละบทความที่ตีพิมพ์ในวารสารวิชาการเล่มนี้ เป็น ความคิดเห็นส่วนตัวของผู้เขียนแต่ละท่าน ไม่เกี่ยวข้องกับสถาบันเทคโนโลยีไทย-ญี่ปุ่น และคณาจารย์ท่านอื่น ๆ ในสถาบัน แต่อย่างใด ความรับผิดชอบด้านเนื้อหาและการตรวจร่างบทความแต่ละบทความเป็นของผู้เขียนแต่ละท่าน หากมีความผิดพลาดใด ๆ ผู้เขียนแต่ละท่านจะต้องรับผิดชอบบทความของตนเองแต่ผู้เดียว
กองบรรณาธิการขอสงวนสิทธิ์มิให้นำเนื้อหา ทัศนะ หรือข้อคิดเห็นใด ๆ ของบทความในวารสารสถาบันเทคโนโลยีไทย-ญี่ปุ่น ไปเผยแพร่ก่อนได้รับอนุญาตจากผู้นิพนธ์ อย่างเป็นลายลักษณ์อักษร ผลงานที่ได้รับการตีพิมพ์ถือเป็นลิขสิทธิ์ของวารสารสถาบันเทคโนโลยีไทย-ญี่ปุ่น
ผู้ประสงค์จะส่งบทความเพื่อตีพิมพ์ในวารสารวิชาการ สถาบันเทคโนโลยีไทย-ญี่ปุ่น สามารถส่ง 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
เอกสารอ้างอิง
J. M. Chang, C. C. Hsu, Y. L. Wang, and T. Y. Ho, “Finding the set of all hinge vertices for strongly chordal graphs in linear time,” Inf. Sci., vol. 99, no. 3-4, pp. 173–182, 1997.
H. Honma and S. Masuyama, “A parallel algorithm for finding all hinge vertices of an interval graph,” IEICE Trans. Inf. & Syst., vol. E84-D, no. 3, pp. 419–423, 2001.
H. Honma, Y. Nakajima, Y. Igarashi, and S. Masuyama, “Algorithm for finding maximum detour hinge vertices of interval graphs,” IEICE Trans. Fundam. Electron. Commun. Comput. Sci., vol. E97-A, no. 6, pp. 1365–1369, 2014.
M. Pal, “Intersection graphs: An introduction,” Annals Pure Appl. Math. (APAM), vol. 4, no. 1, pp. 43–91, 2013.
R. M. McConnell, “Linear-time recognition of circular-arc graphs,” Algorithmica, vol. 37, pp. 93–147, 2003.
M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. New York, NY, USA: Academic Press, 1980.
T. Y. Ho, Y. L. Wang, and M. T. Juan, “A linear time algorithm for finding all hinge vertices of a permutation graph,” Inf. Process. Lett., vol. 59, no. 2, pp. 103–107, 1996.
H. Honma, K. Abe, and S. Masuyama, “Erratum and addendum to a linear time algorithm for finding all hinge vertices of a permutation graph,” Inf. Process. Lett., vol. 111, no. 18, pp. 891–894, 2011.
F. R. Hsu, M. 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, pp. 627–642, 2005.
H. Honma and S. Masuyama, “An optimal parallel algorithm for finding all hinge vertices of a circular-arc graph,” IEICE Trans. Fundam. Electron. Commun. Comput., vol. E91.A, no. 1, pp. 383–391, 2008.
D. Bera, M. Pal, and T. K. Pal, “An efficient algorithm for finding all hinge vertices on trapezoid graphs,” Theory Comput. Syst., vol. 36, no. 1, pp. 17–27, 2003.
H. Honma, Y. Nakajima, and S. Masuyama, “An algorithm for hinge vertex problem on circular trapezoid graphs,” J. Inf. Process., vol. 25, pp. 945–948, 2017.
H. Honma, Y. Nakajima, Y. Igarashi, and S. Masuyama, “Algorithm for identifying the maximum detour hinge vertices of a permutation graph,” IEICE Trans. Fundam. Electron. Commun. Comput., vol. E98-A, no. 6, pp. 1161–1167, 2015.
H. Honma, Y. Nakajima, and S. Masuyama, “An algorithm for the influential hinge vertex problem on interval graphs,” J. Inf. Process., vol. 28, pp. 1047–1051, 2020.
