O(m log n) Split Decomposition of Strongly Connected Graphs

机译：强连通图的O（m log n）拆分分解

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

In the early 1980's, Cunningham described a unique decomposition of a strongly-connected graph. A linear time bound for finding it in the special case of an undirected graph has been given previously, but up until now, the best bound known for the general case has been O(n~3). We give an O(m log n) bound.

机译：在1980年代初期，坎宁安（Cunningham）描述了强连通图的独特分解。先前已经给出了在无向图的特殊情况下找到它的线性时限，但是直到现在，对于一般情况已知的最佳时限是O（n〜3）。我们给定O（m log n）界。

著录项

来源
《Graph theory, computational intelligence and thought : Essays dedicated to Martin Charles Golumbic on the occasion of his 60th birthday》|2008年|158-171|共14页
会议地点 Haifa(IL)
作者
Benson L. Joeris; Scott Lundberg; Ross M. McConnell;
展开▼
作者单位

Trinity College, Cambridge, CB2 1TQ, UK;

Computer Science Department, Colorado State University, Fort Collins, CO 80523-1873;

Computer Science Department, Colorado State University, Fort Collins, CO 80523-1873;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类人工智能理论;
关键词
split decomposition; join decomposition; strongly connected graphs;

机译：分解连接分解强连接图;

相似文献

外文文献
中文文献
专利

1. O(m log n) split decomposition of strongly-connected graphs [J] . Joeris BL, Lundberg S, McConnell RM Discrete Applied Mathematics . 2010,第7期

机译：强连通图的O（m log n）拆分分解
2. Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs (Conference Paper) [J] . Gioan E., Paul C. Discrete Applied Mathematics . 2012,第6期

机译：拆分分解树和图标记树：完全可分解图的特征和全动态算法（会议论文）
3. DECOMPOSITION OF A 2-CONNECTED GRAPH INTO THREE CONNECTED SUBGRAPHS [J] . D. V. Karpov Journal of Mathematical Sciences . 2019,第5期

机译：将2个连通图分解为三个连通子图
4. An O(log n)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs [C] . Ken-ichi Kawarabayashi, Yusuke Kobayashi Approximation, randomization, and combinatorial optimization : Algorithms and techniques . 2010

机译：欧拉平面图和四边连接平面图中不相交路径问题的O（log n）逼近算法
5. Applications of Lexicographic Breadth-First Search to Modular Decomposition, Split Decomposition, and Circle Graphs. [D] . Tedder, Marc. 2011

机译：词法广度优先搜索在模块化分解，拆分分解和圆图上的应用。
6. Decomposition of protein tryptophan fluorescence spectra into log-normal components. I. Decomposition algorithms. [O] . E A Burstein, S M Abornev, Y K Reshetnyak 2001

机译：蛋白色氨酸荧光光谱分解为对数正态分量。一分解算法。
7. O(m log n) Split Decomposition of Strongly Connected Graphs [O] . Benson L. Joeris, Scott Lundberg, Ross M. Mcconnell 2013

机译：强连通图的O（m log n）拆分分解
8. An n LOG n Algorithm for Isomorphism of Planar Triply Connected Graphs [R] . Hopcroft, J. 1970

机译：一种平面三次连通图同构的n LOGn算法

O(m log n) Split Decomposition of Strongly Connected Graphs

摘要

著录项

相似文献

相关主题

期刊订阅