DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cho, Kyungjin | - |
dc.contributor.author | OH, EUNJIN | - |
dc.contributor.author | Oh, Seunghyeok | - |
dc.date.accessioned | 2024-01-23T00:33:09Z | - |
dc.date.available | 2024-01-23T00:33:09Z | - |
dc.date.created | 2023-12-11 | - |
dc.date.issued | 2023-01-24 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/119859 | - |
dc.description.abstract | In this paper, we study the Planar Disjoint Paths problem: Given an undirected planar graph G with n vertices and a set T of k pairs (si, ti)(Equation presented) of vertices, the goal is to find a set P of k pairwise vertex-disjoint paths connecting si and ti for all indices i ∈ {1, ..., k}. We present a (Equation presented)-time algorithm for the Planar Disjoint Paths problem. This improves the two previously best-known algorithms: (Equation presented)-time algorithm [Discrete Applied Mathematics 1995] and (Equation presented)-time algorithm [STOC 2020]. | - |
dc.language | English | - |
dc.publisher | Association for Computing Machinery | - |
dc.relation.isPartOf | 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 | - |
dc.relation.isPartOf | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms | - |
dc.title | Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in k2 and Linear in n | - |
dc.type | Conference | - |
dc.type.rims | CONF | - |
dc.identifier.bibliographicCitation | 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pp.3734 - 3758 | - |
dc.citation.conferenceDate | 2023-01-22 | - |
dc.citation.conferencePlace | IT | - |
dc.citation.endPage | 3758 | - |
dc.citation.startPage | 3734 | - |
dc.citation.title | 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 | - |
dc.contributor.affiliatedAuthor | OH, EUNJIN | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.