ATTENTION: The software behind KU ScholarWorks is being upgraded to a new version. Starting July 15th, users will not be able to log in to the system, add items, nor make any changes until the new version is in place at the end of July. Searching for articles and opening files will continue to work while the system is being updated.
If you have any questions, please contact Marianne Reed at mreed@ku.edu .
Parallel Transitive Closure and Point Location in Planar Structures
dc.contributor.author | Tamassia, Roberto | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2011-03-16T15:41:12Z | |
dc.date.available | 2011-03-16T15:41:12Z | |
dc.date.issued | 1991-08 | |
dc.identifier.citation | R. Tamassia and J. S. Vitter. “Parallel Transitive Closure and Point Location in Planar Structures,” SIAM Journal on Computing, 20(4), August 1991, 708–725. An extended abstract appears in “Optimal Parallel Algorithms for Transitive Closure and Point Location in Planar Structures,” Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA ’89), Sante Fe, NM, June 1989, 399–408. Also appears as an invited paper in Proceedings of the International Workshop on Discrete Algorithms and Complexity, Fukuoka, Japan, November 1989, 169–178. http://dx.doi.org/10.1137/0220045 | |
dc.identifier.uri | http://hdl.handle.net/1808/7171 | |
dc.description | AMS(MOS) subject classifications. 68E05, 68C05, 68C25 | |
dc.description.abstract | Parallel algorithms for several graph and geometric problems are presented, including transitive closure and topological sorting in planar st-graphs, preprocessing planar subdivisions for point location queries, and construction of visibility representations and drawings of planar graphs. Most of these algorithms achieve optimal O(logn) running time using n/logn processors in the EREW PRAM model, n being the number of vertices. | |
dc.language.iso | en_US | |
dc.publisher | Society for Industrial and Applied Mathematics | |
dc.subject | Parallel algorithms | |
dc.subject | Parallel computation | |
dc.subject | Graph algorithm | |
dc.subject | Planar st-graphs | |
dc.subject | Transitive closure | |
dc.subject | Reachability | |
dc.subject | Planar point location | |
dc.subject | Computational geometry | |
dc.subject | Fractional cascading | |
dc.subject | Graph drawing | |
dc.subject | Visibility | |
dc.title | Parallel Transitive Closure and Point Location in Planar Structures | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffrey Scott | |
kusw.oastatus | fullparticipation | |
dc.identifier.doi | 10.1137/0220045 | |
kusw.oaversion | Scholarly/refereed, publisher version | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess |