DC Field | Value | Language |
---|---|---|
dc.contributor.author | OH, EUNJIN | - |
dc.contributor.author | 안신우 | - |
dc.date.accessioned | 2022-11-08T06:50:02Z | - |
dc.date.available | 2022-11-08T06:50:02Z | - |
dc.date.created | 2022-11-08 | - |
dc.date.issued | 2022-10 | - |
dc.identifier.issn | 0178-4617 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/114297 | - |
dc.description.abstract | Let P be a set of n points in the plane where each point p of P is associated with a radius r(p) > 0. The transmission graph G = (P, E) of P is defined as the directed graph such that E contains an edge from p to q if and only if vertical bar pq vertical bar <= r(p) for any two points p and q in P, where vertical bar pq vertical bar denotes the Euclidean distance between p and q. In this paper, we present a data structure of size O(n(5/3)) such that for any two points in P, we can check in O(n(2/3)) time if there is a path in G between the two points. This is the first data structure for answering reachability queries whose performance depends only on n but not on the ratio between the largest and smallest radii. | - |
dc.language | English | - |
dc.publisher | Springer Verlag | - |
dc.relation.isPartOf | Algorithmica | - |
dc.title | Reachability Problems for Transmission Graphs | - |
dc.type | Article | - |
dc.identifier.doi | 10.1007/s00453-022-00985-1 | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | Algorithmica, v.84, no.10, pp.2820 - 2841 | - |
dc.identifier.wosid | 000810313200001 | - |
dc.citation.endPage | 2841 | - |
dc.citation.number | 10 | - |
dc.citation.startPage | 2820 | - |
dc.citation.title | Algorithmica | - |
dc.citation.volume | 84 | - |
dc.contributor.affiliatedAuthor | OH, EUNJIN | - |
dc.identifier.scopusid | 2-s2.0-85131804200 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.isOpenAccess | N | - |
dc.type.docType | Article | - |
dc.subject.keywordAuthor | Geometric intersection graphs | - |
dc.subject.keywordAuthor | Reachability oracles | - |
dc.subject.keywordAuthor | Transmission graphs | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Software Engineering | - |
dc.relation.journalWebOfScienceCategory | Mathematics, Applied | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
dc.relation.journalResearchArea | Mathematics | - |
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.