著者

金子 美博 谷口泰一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2004, no.109, pp.9-15, 2004-11-05

---

ネットワーク構造のシステムにおいて,ある頂点のbetweenness値は,他の2頂点間の最短路に,その頂点がどの程度深く関わっているかを示す尺度の一つである.一般的に,全点対最短路問題を解けば,頂点数nのグラフに対して,O(n3)でbetweenness値は容易に求められる.本報告では,無向の区間グラフを扱う.考察の結果,そのようなグラフでの1個の頂点のbetweenness値をO(n)で求めるアルゴリズムを提案する.In a network system, the betweenness of a vertex is one of measures that shows how deeply that vertex relates to shortest paths between other vertices.Generally,based on all pair shortest path algorithms,we can easily obtain all betweenness for graphs with n vertices in O(n*n*n) time complexity. In this report, we deal with betweenness of vertices on undirected interval graphs.We propose an O(n ) algorithm to calculate betweenness of one vertex on such graph with n vertices.