Parallel Transitive Closure and Point Location in Planar Structures

Tamassia, Roberto; Vitter, Jeffrey Scott

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

Files in this item

Name:: vitter_1991.pdf
Size:: 2.293Mb
Format:: PDF

View/Open

This item appears in the following Collection(s)

The University of Kansas prohibits discrimination on the basis of race, color, ethnicity, religion, sex, national origin, age, ancestry, disability, status as a veteran, sexual orientation, marital status, parental status, gender identity, gender expression and genetic information in the University’s programs and activities. The following person has been designated to handle inquiries regarding the non-discrimination policies: Director of the Office of Institutional Opportunity and Access, IOA@ku.edu, 1246 W. Campus Road, Room 153A, Lawrence, KS, 66045, (785)864-6414, 711 TTY.