Algorithm for Solving the Detour Hinge Vertex Problem on Circular-arc Graphs
Yoko Nakajima, Shoma Nameki, Tomonari Izumi, Hirotoshi Honma · Journal of Engineering and Digital Technology (JEDT) · 2023
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.