Decrease in the time of graph search on original-complement-mixed representations

4 References
  • FUJITA Masato
    Toyohasi University of Technology Department of Information and Computer Sciences
  • ITO Hiro
    Toyohasi University of Technology Department of Information and Computer Sciences
  • UEHARA Hideyuki
    Toyohasi University of Technology Department of Information and Computer Sciences
  • YOKOYAMA Mitsuo
    Toyohasi University of Technology Department of Information and Computer Sciences

Bibliographic Information

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

Search this article

Description

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 graph, 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.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 63 41-48, 1998-07-22

    Information Processing Society of Japan (IPSJ)

References(4)*help

See more

Details 詳細情報について

  • CRID
    1570291227233474816
  • NII Article ID
    110002812145
  • NII Book ID
    AN1009593X
  • ISSN
    09196072
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top