2024-03-29T09:39:18Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001850962022-10-21T05:24:51Z00581:08997:09010
An Algorithm for Hinge Vertex Problem on Circular Trapezoid GraphsAn Algorithm for Hinge Vertex Problem on Circular Trapezoid Graphseng[一般論文(テクニカルノート)] design and analysis of algorithms, hinge vertex problem, intersection graphs, circular trapezoid graphshttp://id.nii.ac.jp/1001/00185008/Journal Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=185096&item_no=1&attribute_id=1&file_no=1Copyright (c) 2017 by the Information Processing Society of JapanDepartment of Creative Engineering, National Institute of Technology, Kushiro CollegeDepartment of Creative Engineering, National Institute of Technology, Kushiro CollegeDepartment of Computer Science and Engineering, Toyohashi University of TechnologyHirotoshi, HonmaYoko, NakajimaShigeru, MasuyamaLet G=(V, E) be a simple connected graph. A vertex u ∈ V is called a hinge vertex if there exist two vertices x and y in G whose distance increases when u is removed. Finding all hinge vertices of a given graph is called the hinge vertex problem. This problem can be applied to improve the stability and robustness of communication network systems. In a number of graph problems, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. Circular trapezoid graphs are proper super-classes of trapezoid graphs. In this paper, we propose an O(n2) time algorithm for the hinge vertex problem of circular trapezoid graphs.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.945------------------------------Let G=(V, E) be a simple connected graph. A vertex u ∈ V is called a hinge vertex if there exist two vertices x and y in G whose distance increases when u is removed. Finding all hinge vertices of a given graph is called the hinge vertex problem. This problem can be applied to improve the stability and robustness of communication network systems. In a number of graph problems, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. Circular trapezoid graphs are proper super-classes of trapezoid graphs. In this paper, we propose an O(n2) time algorithm for the hinge vertex problem of circular trapezoid graphs.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.945------------------------------AN00116647情報処理学会論文誌58122017-12-151882-77642017-12-15