Factorization and pseudofactorization of weighted graphs
Factorization and pseudofactorization of weighted graphs
复制标题
DOI：
10.1016/j.dam.2023.04.019
复制
发表时间：
2021-12
影响因子：
1.1
通讯作者：
Kristin Sheridan;Joseph Berleant;M. Bathe;A. Condon;V. V. Williams-V.
中科院分区：
文献类型：
--
作者：
Kristin Sheridan;Joseph Berleant;M. Bathe;A. Condon;V. V. Williams-V.
对于无权图，求图G的等距嵌入与将图G分解为更小图的笛卡尔积密切相关。当G同构于一个笛卡尔图积时，我们称这个积的因子为G的因子分解。当G同构于笛卡尔积图的等距子图时，我们称这些因子为G的伪因子分解。先前的工作已经表明，一个未加权图的伪因子分解可以用来生成一个规范的等距嵌入到一个产品的最小可能的伪因子。然而，对于任意加权图，它代表了更丰富的度量空间，方法寻找等距嵌入或确定其存在性仍然难以捉摸，实际上伪因子分解和因子分解以前没有扩展到这种情况下。在这项工作中，我们解决的问题，找到一个加权图G的因子分解和伪因子分解，其中G满足的性质，每个边缘构成其端点之间的最短路径。我们把这样的图称为最小图，注意到每个图都可以通过删除不影响其路径度量的边来使其最小。我们将伪因子分解和因子分解推广到极小图，并开发了新的证明技术，扩展了Graham和Winkler（1985）和Feder（1992）提出的用于无权图的伪因子分解和因子分解的算法。我们发现，任何n-顶点，m-边图的正整数边权重可以在O（m2）的时间，加上时间找到所有对最短路径（APSP）的距离在一个加权图，导致在O（m2 + n2 log log n）的时间的整体运行时间。我们还表明，这样一个图的伪因子分解可以计算在O（MN）的时间，加上时间来解决APSP，导致在O（MN + N 2 log log n）的运行时间。
For unweighted graphs, finding isometric embeddings of a graph G is closely related to decompositions of G into Cartesian products of smaller graphs. When G is isomorphic to a Cartesian graph product, we call the factors of this product a factorization of G. When G is isomorphic to an isometric subgraph of a Cartesian graph product, we call those factors a pseudofactorization of G. Prior work has shown that an unweighted graph’s pseudofactorization can be used to generate a canonical isometric embedding into a product of the smallest possible pseudofactors. However, for arbitrary weighted graphs, which represent a richer variety of metric spaces, methods for finding isometric embeddings or determining their existence remain elusive, and indeed pseudofactorization and factorization have not previously been extended to this context. In this work, we address the problem of finding the factorization and pseudofactorization of a weighted graph G, where G satisfies the property that every edge constitutes a shortest path between its endpoints. We term such graphs minimal graphs, noting that every graph can be made minimal by removing edges not affecting its path metric. We generalize pseudofactorization and factorization to minimal graphs and develop new proof techniques that extend the previously proposed algorithms due to Graham and Winkler (1985) and Feder (1992) for pseudofactorization and factorization of unweighted graphs. We show that any n-vertex, m-edge graph with positive integer edge weights can be factored in O (m 2) time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of O (m 2+ n 2 log log n) time. We also show that a pseudofactorization for such a graph can be computed in O (m n) time, plus the time to solve APSP, resulting in an O (m n+ n 2 log log n) running time.