论文标题
在加权的司额分离器上
On weighted sublinear separators
论文作者
论文摘要
考虑一个图形G，并分配了对顶点的成本。即使G及其所有子图都承认了均方根尺寸的平衡分离器，G也只能在删除一小部分特殊顶点的Z之后承认平衡的sublinear成本分离器。我们改善了| z |的界限。从o（log | v（g）|）到o（对数的任何固定数量的迭代，log log ... log | v（g）|）。
Consider a graph G with an assignment of costs to vertices. Even if G and all its subgraphs admit balanced separators of sublinear size, G may only admit a balanced separator of sublinear cost after deleting a small set Z of exceptional vertices. We improve the bound on |Z| from O(log |V(G)|) to O(log log...log |V(G)|), for any fixed number of iterations of the logarithm.
