文章基本信息

标题：Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs
本地全文：下载
作者：Gupta, Chetan ; Jain, Rahul ; Tewari, Raghunath 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：213
DOI：10.4230/LIPIcs.FSTTCS.2021.23
语种：English
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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/2} n^{1/2} log n)-space to find an O(g^{1/2} n^{1/2})-sized separator of a graph having n vertices and embedded on an orientable surface of genus g.
关键词：Graph algorithms;space-bounded algorithms;surface embedded graphs;reachability;Euler genus;algorithmic graph theory;computational complexity theory