On weighted sublinear separators | Zendy

Dvořák Zdeněk | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

On weighted sublinear separators

Author(s) -

Dvořák Zdeněk

Publication year - 2022

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.22777

Subject(s) - sublinear function , mathematics , combinatorics , logarithm , separator (oil production) , graph , discrete mathematics , upper and lower bounds , mathematical analysis , physics , thermodynamics

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research