Parallel Transitive Closure and Point Location in Planar Structures

DOI10.1137/0220045MaRDI QIDQ3978176zbMATH OpenOpenAlexFDO

Authors Roberto Tamassia, Jeffrey Scott Vitter

Publication date 25 June 1992

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1808/7171

zbMATH Keywords

fractional cascadinggraph drawingplanar \(st\)-graphsplanar point locationreachabilityvisibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed algorithms (68W15)

Recommendations

• Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
• High-Probability Parallel Transitive-Closure Algorithms
• Optimal parallel algorithms on planar graphs
• Efficient parallel algorithms for planar st-graphs
• scientific article; zbMATH DE number 4060742

Cited in

(14)

• Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
• A near-linear algorithm for the planar segment-center problem
• Bipolar orientations revisited
• An efficient parallel algorithm for finding rectangular duals of plane triangular graphs
• An efficient parallel algorithm for shortest paths in planar layered digraphs
• A time-optimal parallel algorithm for three-dimensional convex hulls
• Optimal cooperative search in fractional cascaded data structures
• Designing checkers for programs that run in parallel
• Selecting distances in the plane
• High-Probability Parallel Transitive-Closure Algorithms
• scientific article; zbMATH DE number 1948455 (Why is no real title available?)
• Parallel batched planar point location on the CCC
• Parallel algorithms for planar dominance counting
• Approximating nearest neighbor among triangles in convex position

This page was built for publication: Parallel Transitive Closure and Point Location in Planar Structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3978176)