Parallel Transitive Closure and Point Location in Planar Structures | Zendy

Roberto Tamassia | Zendy; Jeffrey Scott Vitter | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Parallel Transitive Closure and Point Location in Planar Structures

Author(s) -

Roberto Tamassia,

Jeffrey Scott Vitter

Publication year - 1991

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0220045

Subject(s) - transitive closure , planar graph , planar , combinatorics , transitive relation , closure (psychology) , computer science , preprocessor , mathematics , point location , graph , sorting , point (geometry) , discrete mathematics , algorithm , geometry , computer graphics (images) , artificial intelligence , economics , market economy

We present parallel algorithms for several graph and geometric problems, including transitive closure and topological sorting in planar {\em 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( \log n)$ running time using $ n / \log n $ processors in the EREW PRAM model, $n$ being the number of vertices.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research