Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs
share
A graph separator is a subset of vertices of a graph whose removal divides the graph into small components. Computing small graph separators for various classes of graphs is an important computational task. In this paper, we present a polynomial time algorithm that uses O(g^1/2n^1/2log n)-space to find an O(g^1/2n^1/2)-sized separator of a graph having n vertices and embedded on a surface of genus g.
READ FULL TEXT