Article ID Journal Published Year Pages File Type
8903571 European Journal of Combinatorics 2018 11 Pages PDF
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
,