k-辺連結性を保存する疎なグラフを求める効率の良いNCアルゴリズム

10 References
  • NAGAMOCHI Hiroshi
    Department of Applied Mathematics and Physics Graduate School of Informatics, Kyoto University
  • HASUNUMA Toru
    Department of Applied Mathematics and Physics Graduate School of Informatics, Kyoto University

Bibliographic Information

Other Title
  • An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificate

Search this article

Description

多重グラフGのk-辺連結性を保持する疎な全域部分多重グラフを、CRCW(ARBITRARY)PRAM上でO(k(n+m'))個のプロセッサを使用し、O((logkn)(logk)^2(logn)^2))時間で計算するNCアルゴリズムを与える。ここで、nはGの頂点数、m'はGを単純化して得られるグラフの辺の数を表す。
We present an efficient NC algorithm for finding a sparse k-edge-connectivity certificate of a multi-graph G. Our algorithm runs in O((logkn)(logk)^2(logn)^2)) time using O(k(n+m')) processors on a CRCW(ARBITRARY)PRAM, where n and m' stand for the numbers of vertices in G and edges in the simplified graph of G, respectively.

Journal

References(10)*help

See more

Keywords

Details 詳細情報について

  • CRID
    1570854177377034112
  • NII Article ID
    110003191664
  • NII Book ID
    AN10013152
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top