2026-07-22T18:45:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15534 2024-03-06T10:55:32Z ddc:004 open_access

Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs Gupta, Chetan Jain, Rahul Tewari, Raghunath Graph algorithms space-bounded algorithms surface embedded graphs reachability Euler genus algorithmic graph theory computational complexity theory 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chetan Gupta and Rahul Jain and Raghunath Tewari 2021 Is Part Of LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2021.23 urn:nbn:de:0030-drops-155344 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.23 eng https://creativecommons.org/licenses/by/4.0/legalcode