Linear Time Algorithms for Finding Articulation and Hinge Vertices of Circular Permutation Graphs
-
- HONMA Hirotoshi
- Department of Information Engineering, Kushiro National College of Technology
-
- ABE Kodai
- Department of Intelligent Interaction Technologies, University of Tsukuba
-
- NAKAJIMA Yoko
- Department of Information Engineering, Kushiro National College of Technology
-
- MASUYAMA Shigeru
- Department of Computer Science and Engineering, Toyohashi University of Technology
この論文をさがす
説明
Let Gs=(Vs,Es) be a simple connected graph. A vertex v ∈ Vs is an articulation vertex if deletion of v and its incident edges from Gs disconnects the graph into at least two connected components. Finding all articulation vertices of a given graph is called the articulation vertex problem. A vertex u ∈ Vs is called a hinge vertex if there exist any two vertices x and y in Gs whose distance increase when u is removed. Finding all hinge vertices of a given graph is called the hinge vertex problem. These problems can be applied to improve the stability and robustness of communication network systems. In this paper, we propose linear time algorithms for the articulation vertex problem and the hinge vertex problem of circular permutation graphs.
収録刊行物
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E96.D (3), 419-425, 2013
一般社団法人 電子情報通信学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1390001204379678848
-
- NII論文ID
- 10031167426
-
- NII書誌ID
- AA10826272
-
- ISSN
- 17451361
- 09168532
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可