Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
CSE Conference and Workshop Papers
Reachability; surface-embedded graphs; acyclic digraph; log-space algorithm
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Space-Efficient Algorithms For Reachability In Surface-Embedded Graphs, Derrick Stolee, N. V. Vinodchandran
Space-Efficient Algorithms For Reachability In Surface-Embedded Graphs, Derrick Stolee, N. V. Vinodchandran
CSE Conference and Workshop Papers
This work presents a log-space reduction which compresses an n-vertex directed acyclic graph with m(n) sources embedded on a surface of genus g(n), to a graph with O(m(n) + g(n)) vertices while preserving reachability between a given pair of vertices. Applying existing algorithms to this reduced graph yields new deterministic algorithms with improved space bounds as well as improved simultaneous time space bounds for the reachability problem over a large class of directed acyclic graphs. Specifically, it significantly extends the class of surface-embedded graphs with log-space reachability algorithms: from planar graphs with O(log n) sources, to graphs with …