Routing by matching on convex pieces of grid graphs
Routing by matching on convex pieces of grid graphs
复制标题
通过匹配网格图的凸块进行路由
DOI：
10.1016/j.comgeo.2022.101862
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Yang, H.
中科院分区：
文献类型：
--
作者：
Alpert, H.;Barnes, R.;Bell, S.;Mauro, A.;Nevo, N.;Tucker, N.;Yang, H.
路由数是由Alon，Chung和Graham在1994年引入的图不变量，并且已经针对树和其他类别的图（如超立方体）进行了研究。它给出了对一组不同的标记进行排序所需的最小路由步骤数，每个顶点上放置一个标记，其中每个路由步骤交换一组不相交的相邻标记对。我们的主要定理推广了已知的估计：一个宽为w（R），高为h（R）的矩形格图R满足rt（R）∈ O（w（R）+ h（R））.本文证明了：对于被任意凸多边形包围的无限正方形格的子图P，有rt（P）∈ O（w（P）+ h（P））.
The routing number is a graph invariant introduced by Alon, Chung, and Graham in 1994, and it has been studied for trees and other classes of graphs such as hypercubes. It gives the minimum number of routing steps needed to sort a set of distinct tokens, placed one on each vertex, where each routing step swaps a set of disjoint pairs of adjacent tokens. Our main theorem generalizes the known estimate that a rectangular grid graph R with width w (R) and height h (R) satisfies rt (R)∈ O (w (R)+ h (R)). We show that for the subgraph P of the infinite square lattice enclosed by any convex polygon, we have rt (P)∈ O (w (P)+ h (P)).
登录
查看更多内容
DOI：
10.4230/lipics.socg.2018.29
发表时间：
2018-01
期刊：
--
影响因子：
--
作者：
E. Demaine;S. Fekete;Phillip Keldenich;H. Meijer;Christian Scheffer
通讯作者：
E. Demaine;S. Fekete;Phillip Keldenich;H. Meijer;Christian Scheffer
通过匹配在图上进行路由排列
DOI：
10.1145/167088.167239
发表时间：
1993
期刊：
Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
N. Alon;F. C. Graham;R. Graham
通讯作者：
R. Graham
正方形和六边形的离散配置空间
DOI：
10.1007/s41468-019-00043-w
发表时间：
2020
期刊：
Journal of Applied and Computational Topology
影响因子：
--
作者：
Alpert, Hannah
通讯作者：
Alpert, Hannah
在极端密度下协调带标签光盘的运动并保证最优性
DOI：
--
发表时间：
2018
期刊：
International Workshop on the Algorithmic Foundations of Robotics
影响因子：
--
作者：
Chinta, Rupesh;Han, Shuai D.;Yu, Jingjin
通讯作者：
Yu, Jingjin