Computing k-Edge-Connected Components of a Multigraph (Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we propose an algorithm of O(|V|min{k,|V|,√<|A|>}|A|) time complexity for finding all k-edge-connected components of a given digraph D=(V,A) and a positive integer k. When D is symmetric, incorporating a preprocessing reduces this time complexity to O(|A|+|V|^2+ |V|min{k,|V|}min{k|V|,|A|}), which is at most O(|A|+k^2|V|^2).

• 社団法人電子情報通信学会の論文
• 1993-04-25

著者

• Watanabe Toshimasa

  The Faculty Of Engineering Hiroshima University

• Nagamochi Hiroshi

  The Faculty Of Engineering Kyoto University

関連論文

• Computing k-Edge-Connected Components of a Multigraph (Special Section on Discrete Mathematics and Its Applications)
• Qualitative Analysis of Periodic Schedules for Deterministically Timed Petri Net Systems (Special Section on Discrete Mathematics and Its Applications)
• A Linear Time Algorithm for Smallest Augmentation to 3Edge-Connect a Graph (Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク