Projects per year
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 language | English |
---|---|
Title of host publication | 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
Subtitle of host publication | FSTTCS 2021, December 15–17, 2021, Virtual Conference |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | 1-15 |
Number of pages | 15 |
ISBN (Electronic) | 978-3-95977-215-0 |
Publication status | Published - 29 Nov 2021 |
MoE publication type | A4 Conference publication |
Event | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - Virtual, Online Duration: 15 Dec 2021 → 17 Dec 2021 Conference number: 41 |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Publisher | Schloss Dagstuhl –Leibniz Center for Informatics |
Volume | 213 |
ISSN (Electronic) | 1868-8969 |
Conference
Conference | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
---|---|
Abbreviated title | FSTTCS |
City | Virtual, Online |
Period | 15/12/2021 → 17/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.Projects
- 1 Finished
-
-: Parallel and distributed computing for Bayesian graphical models
Suomela, J. (Principal investigator)
04/09/2019 → 30/04/2023
Project: Academy of Finland: Other research funding