.png){kind=icon}
返回
An optimal distributed ear decomposition algorithm with applications to biconnectivity and outerplanarity testing
.png){kind=icon}
PRE
AI
DOI：10.1109/71.841748.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We present an asynchronous distributed algorithm to determine an ear decomposition of an arbitrary, connected, bidirectional network containing n-nodes and m-links which uses O(m) messages and which can be completed in O(n) time. Using the ear decomposition, we obtain the following results for a distributed network: 1) The distributed ear decomposition algorithm can be used to test biconnectivity, determine biconnected components. find cutpoints and bridges using O(m) messages in O(n) time. 2) The distributed ear decomposition algorithm can be used to test ii a biconnected network is outerplanar using O(n) messages in O(n) time. and if the network is outerplanar, the embedding is also given using the same message and time complexity.
Keyword:
distributed algorithm
message complexity
ear decomposition
biconnectivity testing
outerplanarity testing
depth first search
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
5.2K
被引数:
1.1W
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏分享收藏
查看更多内容