Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs

Chetan Gupta, Rahul Jain, Raghunath Tewari

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

21 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publication41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Subtitle of host publicationFSTTCS 2021, December 15–17, 2021, Virtual Conference
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages1-15
Number of pages15
ISBN (Electronic)978-3-95977-215-0
Publication statusPublished - 29 Nov 2021
MoE publication typeA4 Conference publication
EventIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - Virtual, Online
Duration: 15 Dec 202117 Dec 2021
Conference number: 41

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl –Leibniz Center for Informatics
Volume213
ISSN (Electronic)1868-8969

Conference

ConferenceIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Abbreviated titleFSTTCS
CityVirtual, Online
Period15/12/202117/12/2021

Fingerprint

Dive into the research topics of 'Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs'. Together they form a unique fingerprint.

Cite this