@techreport{oai:ipsj.ixsq.nii.ac.jp:00032175,
 author = {藤田, 正人 and 伊藤大雄 and 上原, 秀幸 and 横山, 光雄 and Masato, Fujita and Hiro, Ito and Hideyuki, Uehara and Mitsuo, Yokoyama},
 issue = {62(1998-AL-063)},
 month = {Jul},
 note = {単純グラフは補グラフを用いても表現でき、枝数が密である時は補グラフ表現の方がデータ量が少なくてすむ。ただこの表現法によって、これまで線形時間アルゴリズムであるとされてきたものに対して、線形時間可解性が保証されない可能性が生じる。しかし著者らによって、単純グラフに対する既存の線形時間探索アルゴリズムにおいて、補グラフ表現を用いても線形時間で動作するアルゴリズムが提案された。本報告では、グラフのそれぞれの節点の隣接枝数の密度に着目し、グラフ全体での枝数の密度に関係なく、グラフを表現するデータ量が削減できる単純グラフの表現法を提案する。そして、幅優先探索および深さ優先探索に対し、提案する表現法を用いても線形時間で動作するアルゴリズムを提案する。さらに、提案するアルゴリズムの計算時間を数値実験により評価し、その結果からグラフ探索時間の削減が可能であることが示された。, 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.},
 title = {正補混合表現によるグラフ探索時間の削減},
 year = {1998}
}