Publication:2254502

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

Loukas Georgiadis, Leonidas Palios, Stavros D. Nikolopoulos

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

algorithmsreachabilitydata structuresgraph algorithmscombinatorial complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Directed graphs (digraphs), tournaments (05C20)

Related Items

Join-reachability problems in directed graphs

Cites Work

• Unnamed Item
• 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
• Fast Algorithms for Finding Nearest Common Ancestors
• Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs
• Computing Frequency Dominators and Related Problems
• Filtering Search: A New Approach to Query-Answering
• A Separator Theorem for Planar Graphs
• An Efficient Data Structure for Lattice Operations
• Compact oracles for reachability and approximate distances in planar digraphs
• The Transitive Reduction of a Directed Graph
• Depth-First Search and Linear Graph Algorithms
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting