Computing and Listing Avoidable Vertices and Paths
Computing and Listing Avoidable Vertices and Paths
复制标题
计算并列出可避免的顶点和路径
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
A. Zisis
中科院分区：
文献类型：
--
作者：
Charis Papadopoulos;A. Zisis
图的单纯顶点是邻域为团的顶点。众所周知，列出所有单纯顶点可以在 O ( nm ) 时间或 $$O(n^{omega })$$ O ( n ω ) 时间内完成，其中 $$O(n^{omega })$$ O ( n ω ) 是执行快速矩阵乘法所需的时间。可避免顶点的概念通过以下方式概括了单纯顶点的概念：如果具有中间顶点 u 的三个顶点上的每个导出路径都包含在一个导出循环中，则顶点 u 是可避免的。我们提出了通过最小三角剖分和公共邻域检测的概念列出图的所有可避免顶点的算法。特别是，我们分别给出运行时间 $$O(n^{2}m)$$ O ( n 2 m ) 和 $$O(n^{1+omega })$$ O ( n 1 + ω ) 的算法。此外，基于简化图遍历，我们提出了一种快速算法，其运行时间为 $$O(n^2 + m^2)$$ O ( n 2 + m 2 ) ，并与列出稀疏图上所有单纯顶点的相应运行时间 $$m=O(n)$$ m = O ( n ) 相匹配。此外，我们表明我们的算法无法显着改进，因为我们证明在合理的复杂性假设下，不存在真正的次二次算法来识别可避免的顶点。为了补充我们的结果，我们考虑了它们对可避免边缘和可避免路径的自然概括。我们提出了一种 O ( nm ) 时间算法来识别给定的诱导路径是否是可以避免的。
A simplicial vertex of a graph is a vertex whose neighborhood is a clique. It is known that listing all simplicial vertices can be done in O ( nm ) time or $$O(n^{omega })$$ O ( n ω ) time, where $$O(n^{omega })$$ O ( n ω ) is the time needed to perform a fast matrix multiplication. The notion of avoidable vertices generalizes the concept of simplicial vertices in the following way: a vertex u is avoidable if every induced path on three vertices with middle vertex u is contained in an induced cycle. We present algorithms for listing all avoidable vertices of a graph through the notion of minimal triangulations and common neighborhood detection. In particular we give algorithms with running times $$O(n^{2}m)$$ O ( n 2 m ) and $$O(n^{1+omega })$$ O ( n 1 + ω ) , respectively. Additionally, based on a simplified graph traversal we propose a fast algorithm that runs in time $$O(n^2 + m^2)$$ O ( n 2 + m 2 ) and matches the corresponding running time of listing all simplicial vertices on sparse graphs with $$m=O(n)$$ m = O ( n ) . Moreover, we show that our algorithms cannot be improved significantly, as we prove that under plausible complexity assumptions there is no truly subquadratic algorithm for recognizing an avoidable vertex. To complement our results, we consider their natural generalizations of avoidable edges and avoidable paths. We propose an O ( nm )-time algorithm that recognizes whether a given induced path is avoidable.
DOI：
10.48550/arxiv.1205.2535
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Aboulker P
通讯作者：
Aboulker P