Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs
| dc.contributor | Aalto-yliopisto | fi |
| dc.contributor | Aalto University | en |
| dc.contributor.author | Gupta, Chetan | en_US |
| dc.contributor.author | Jain, Rahul | en_US |
| dc.contributor.author | Tewari, Raghunath | en_US |
| dc.contributor.department | Department of Computer Science | en |
| dc.contributor.groupauthor | Professorship Suomela J. | en |
| dc.contributor.organization | Fernuniversität in Hagen | en_US |
| dc.contributor.organization | Indian Institute of Technology Kanpur | en_US |
| dc.date.accessioned | 2021-12-08T07:33:19Z | |
| dc.date.available | 2021-12-08T07:33:19Z | |
| dc.date.issued | 2021-11-29 | en_US |
| dc.description.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. | en |
| dc.description.version | Peer reviewed | en |
| dc.format.extent | 15 | |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.citation | Gupta, C, Jain, R & Tewari, R 2021, Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs. in 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science : FSTTCS 2021, December 15–17, 2021, Virtual Conference., 23, Leibniz International Proceedings in Informatics (LIPIcs), vol. 213, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-15, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Virtual, Online, 15/12/2021. < https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=15534 > | en |
| dc.identifier.isbn | 978-3-95977-215-0 | |
| dc.identifier.issn | 1868-8969 | |
| dc.identifier.other | PURE UUID: e29d4327-df35-4987-93d5-30e1e5f2c7ac | en_US |
| dc.identifier.other | PURE ITEMURL: https://research.aalto.fi/en/publications/e29d4327-df35-4987-93d5-30e1e5f2c7ac | en_US |
| dc.identifier.other | PURE LINK: https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=15534 | en_US |
| dc.identifier.other | PURE FILEURL: https://research.aalto.fi/files/76360030/Time_Space_Optimal_Algorithm_for_Computing_Separators_in_Bounded_Genus_Graphs.pdf | en_US |
| dc.identifier.uri | https://aaltodoc.aalto.fi/handle/123456789/111498 | |
| dc.identifier.urn | URN:NBN:fi:aalto-2021120810642 | |
| dc.language.iso | en | en |
| dc.relation.ispartof | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science | en |
| dc.relation.ispartofseries | 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science: FSTTCS 2021, December 15–17, 2021, Virtual Conference | en |
| dc.relation.ispartofseries | pp. 1-15 | en |
| dc.relation.ispartofseries | Leibniz International Proceedings in Informatics (LIPIcs) ; Volume 213 | en |
| dc.rights | openAccess | en |
| dc.title | Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs | en |
| dc.type | A4 Artikkeli konferenssijulkaisussa | fi |
| dc.type.version | publishedVersion |