正補混合表現によるグラフ探索時間の削減

• Item type: SIG Technical Reports(1)
• 公開日: 1998-07-22
• タイトル: 正補混合表現によるグラフ探索時間の削減
• タイトル / 言語: en
• タイトル: Decrease in the time of graph search on original -complement- mixed representations
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 豊橋技術科学大学情報工学系
• 著者所属: 豊橋技術科学大学情報工学系
• 著者所属: 豊橋技術科学大学情報工学系
• 著者所属: 豊橋技術科学大学情報工学系
• 著者所属(英): en
• 著者所属(英): Toyohasi University of Tecnology Department of Information and Computer Sciences
• 著者所属(英): en
• 著者所属(英): Toyohasi University of Tecnology Department of Information and Computer Sciences
• 著者所属(英): en
• 著者所属(英): Toyohasi University of Tecnology Department of Information and Computer Sciences
• 著者所属(英): en
• 著者所属(英): Toyohasi University of Tecnology Department of Information and Computer Sciences
• 著者名: 藤田, 正人; 伊藤大雄; 上原, 秀幸; 横山, 光雄
• 著者名(英): Masato, Fujita; Hiro, Ito; Hideyuki, Uehara; Mitsuo, Yokoyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 単純グラフは補グラフを用いても表現でき、枝数が密である時は補グラフ表現の方がデータ量が少なくてすむ。ただこの表現法によって、これまで線形時間アルゴリズムであるとされてきたものに対して、線形時間可解性が保証されない可能性が生じる。しかし著者らによって、単純グラフに対する既存の線形時間探索アルゴリズムにおいて、補グラフ表現を用いても線形時間で動作するアルゴリズムが提案された。本報告では、グラフのそれぞれの節点の隣接枝数の密度に着目し、グラフ全体での枝数の密度に関係なく、グラフを表現するデータ量が削減できる単純グラフの表現法を提案する。そして、幅優先探索および深さ優先探索に対し、提案する表現法を用いても線形時間で動作するアルゴリズムを提案する。さらに、提案するアルゴリズムの計算時間を数値実験により評価し、その結果からグラフ探索時間の削減が可能であることが示された。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Simple graphs can be represented by the complement graphs. When the complement graph includes smaller number of edges than an original one, using the complement-graph-representation reduces the space of memories for representing a graph. The authors have presented linear time breadth first search (BFS) and depth first serch (DFS) algorithms for the complement graph representations before. This paper presents original-complement-mixed (OCM in short) representations, which decreases the space of memories for representing an original graph. The paper also shows that for a given OCM represented grpah, BFS tree and DFS tree of the original graph can be constructed in linear-time. Furthermore, it shows that the running time of BFS and DFS on the OCM representations are faster than ones of original representations, by computer examinations.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1998, 号 62(1998-AL-063), p. 41-48, 発行日 1998-07-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会