Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903571 | European Journal of Combinatorics | 2018 | 11 Pages |
Abstract
For real numbers c,ε>0, let Gc,ε denote the class of graphs G such that each subgraph H of G has a balanced separator of order at most c|V(H)|1âε. A class G of graphs has strongly sublinear separators if GâGc,ε for some c,ε>0. We investigate properties of such graph classes, leading in particular to an approximate algorithm to determine membership in Gc,ε: there exist câ²>0 such that for each input graph G, this algorithm in polynomial time determines either that GâGcâ²,ε2â160, or that GâGc,ε.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
ZdenÄk DvoÅák,