Linear Time Graph Search Algorithms on Input of Complement Graphs

2 Citations 4 References
  • ITO Hiro
    NTT Telecommunication Networks Laboratories

Bibliographic Information

Other Title
  • 補グラフ入力に対する線形時間グラフ探索アルゴリズム

Search this article

Abstract

For representing a simple graph, a complement graph is sufficient. Thus, a space-saving strategy that representing one (the original graph or the complement graph), which include smaller number of edges can be adopted. While this strategy has no effect on the polynomial solvability of problems, it has a effect on fast algorithms, especially. linear-time algorithms. That is, a linear-time algorithm on traditional input may not be able to run in linear time if instances are represented by the proposed strategy. Therefore, a linear-time width-first- and depth-first-search algorithms for complement graphs are proposed. By using these search algorithms, linear-time algorithms can be created for many problems based on the input of complement graphs.

Journal

Citations (2)*help

See more

References(4)*help

See more

Keywords

Details 詳細情報について

  • CRID
    1571980077283183104
  • NII Article ID
    110003191490
  • NII Book ID
    AN10013152
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top