Join-reachability problems in directed graphs

DOI10.1007/s00224-013-9450-7zbMath1306.05077arXiv1012.4938MaRDI QIDQ2254502

Loukas Georgiadis, Stavros D. Nikolopoulos, Leonidas Palios

Publication date: 5 February 2015

Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.4938

zbMATH Keywords

algorithms; reachability; data structures; graph algorithms; combinatorial complexity

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68P05: Data structures

05C20: Directed graphs (digraphs), tournaments

Related Items

Join-reachability problems in directed graphs

Cites Work

• Unnamed Item
• Dynamic reachability in planar digraphs with one source and one sink
• On the vector representation of the reachability in planar directed graphs
• Join-reachability problems in directed graphs
• Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs
• Computing Frequency Dominators and Related Problems
• An Efficient Data Structure for Lattice Operations
• Compact oracles for reachability and approximate distances in planar digraphs
• The Transitive Reduction of a Directed Graph