"Efficient Enumeration of Subgraphs and Induced Subgraphs with Bounded Girth"
"Efficient Enumeration of Subgraphs and Induced Subgraphs with Bounded Girth"
复制标题
“有界周长的子图和归纳子图的高效枚举”
DOI：
10.1007/978-3-319-94667-2_17
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
and Hiroki Arimura
中科院分区：
文献类型：
--
作者：
Kazuhiro Kurita;Kunihiro Wasa;Alessio Conte;Takeaki Uno;and Hiroki Arimura
图的围长是它的最短圈的长度。由于其在图论，网络分析和实际领域的相关性，如分布式计算，围长相关的问题已经在过去和最近的文献中的关注对象。本文考虑围长有界的连通子图的列问题。由于大围长是稀疏性的指标，这允许从输入图中提取稀疏结构。我们提出了两个算法，分别用于枚举围长有界的顶点诱导子图和边诱导子图，每个解的平均时间都是O（n），而计算空间都是O（n）。此外，该算法可以很容易地适应放宽连通性的要求，并处理加权图。作为一个副产品，第二个算法可以用来回答众所周知的问题，找到girthk的密集顶点图（S）。
The girth of a graph is the length of its shortest cycle. Due to its relevance in graph theory, network analysis and practical fields such as distributed computing, girth-related problems have been object of attention in both past and recent literature. In this paper, we consider the problem of listing connected subgraphs with bounded girth. As a large girth is index of sparsity, this allows to extract sparse structures from the input graph. We propose two algorithms, for enumerating respectively vertex induced subgraphs and edge induced subgraphs with bounded girth, both running inO(n) amortized time per solution and usingspace. Furthermore, the algorithms can be easily adapted to relax the connectivity requirement and to deal with weighted graphs. As a byproduct, the second algorithm can be used to answer the well known question of finding the densestn-vertex graph(s) of girthk.