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