A unified geometric approach to graph separators
A unified geometric approach to graph separators
复制标题
DOI：
10.1109/sfcs.1991.185417
复制
发表时间：
1991-09
期刊：
影响因子：
--
通讯作者：
G. Miller;S. Teng;S. Vavasis
中科院分区：
文献类型：
--
作者：
G. Miller;S. Teng;S. Vavasis
提出了一类称为k重叠图的图。k重叠图的特殊情况包括平面图、k近邻图和与有限元方法相关的早期图类。证明了嵌入在d维的k重叠图的一个分隔界。结果统一了先前的几个分隔符结果。所有的参数都是基于嵌入的几何性质。分隔边界带有随机线性时间和随机NC算法。此外，边界是最好的，直到第一项。b>
A class of graphs called k-overlap graphs is proposed. Special cases of k-overlap graphs include planar graphs, k-nearest neighbor graphs, and earlier classes of graphs associated with finite element methods. A separator bound is proved for k-overlap graphs embedded in d dimensions. The result unifies several earlier separator results. All the arguments are based on geometric properties of embedding. The separator bounds come with randomized linear-time and randomized NC algorithms. Moreover, the bounds are the best possible up to the leading term.>