Back to Search
Start Over
On weighted sublinear separators
- Publication Year :
- 2020
-
Abstract
- 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.<br />Comment: 14 pages, 0 figures. (v2) Correction to the statement and proof of Theorem 6 (v3) minor changes from reviews after reviews
- Subjects :
- Mathematics - Combinatorics
05C75
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2007.11853
- Document Type :
- Working Paper