A Unified Framework for Light Spanners
A Unified Framework for Light Spanners
复制标题
轻型扳手的统一框架
DOI：
10.1145/3564246.3585185
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Shay Solomon
中科院分区：
文献类型：
--
作者：
Hung Le;Shay Solomon
多年来，关于轻扳手的开创性工作为各种图形类中的扳手提供了最佳亮度，例如一般图，欧几里得扳手和无次要图。以前关于轻型扳手的工作有三个缺点：(i)这些结构的运行时间几乎总是次优的，而且通常远非最佳的。这些结构在标准和粗糙的意义上是最优的，但在考虑到更大范围的有关参数的精细意义上则不是。(3)技术是针对图类的，不能广泛应用。这项工作旨在通过在各种图形类中呈现一个统一的光扳手框架来解决这些缺点。非正式地说，该框架归结为从稀疏扳手到轻扳手的转换；由于稀疏扳手的最新技术比轻扳手先进得多，因此这种转换是强大的。首先，我们应用我们的框架为几个图类设计具有最优亮度的快速构造。其次，我们应用我们的框架为几个图类实现更精细的最优性边界，即，当考虑到更广泛的涉及参数时，边界仍然是最优的，最明显的是_。我们的新结构明显优于每个已检查的图类的最先进的结构。
Seminal works on light spanners over the years provide spanners with optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graphs. Three shortcomings of previous works on light spanners are: (i) The runtimes of these constructions are almost always sub-optimal, and usually far from optimal. (ii) These constructions are optimal in the standard and crude sense, but not in a refined sense that takes into account a wider range of involved parameters. (iii) The techniques are ad hoc per graph class, and thus can’t be applied broadly. This work aims at addressing these shortcomings by presenting a unified framework of light spanners in a variety of graph classes. Informally, the framework boils down to a transformation from sparse spanners to light spanners; since the state-of-the-art for sparse spanners is much more advanced than that for light spanners, such a transformation is powerful. First, we apply our framework to design fast constructions with optimal lightness for several graph classes. Second, we apply our framework to achieve more refined optimality bounds for several graph classes, i.e., the bounds remain optimal when taking into account a wider range of involved parameters, most notably є. Our new constructions are significantly better than the state-of-the-art for every examined graph class.
（近）线性时间内一般图的近最优 Spanner
DOI：
10.1137/1.9781611977073.132
发表时间：
2022
期刊：
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Le, Hung;Solomon, Shay
通讯作者：
Solomon, Shay
飞机上的轻型欧几里得斯坦纳扳手
DOI：
10.4230/lipics.socg.2021.15
发表时间：
2021
期刊：
37th International Symposium on Computational Geometry (SoCG 2021
影响因子：
--
作者：
Bhore, Sujoy;Toth, Csaba D.
通讯作者：
Toth, Csaba D.
DOI：
10.1112/jlms.12500
发表时间：
2021
期刊：
Journal of the London Mathematical Society
影响因子：
--
作者：
Conlon, David;Fox, Jacob;Sudakov, Benny;Zhao, Yufei
通讯作者：
Zhao, Yufei