Join-reachability problems in directed graphs. (English) Zbl 1332.68172
Kulikov, Alexander (ed.) et al., Computer science – theory and applications. 6th international computer science symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14–18, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20711-2/pbk). Lecture Notes in Computer Science 6651, 195-208 (2011).
Summary: For a given collection \(\mathcal{G}\) of directed graphs we define the join-reachability graph of \(\mathcal{G}\), denoted by \(\mathcal{J}(\mathcal{G})\), as the directed graph that, for any pair of vertices \(a\) and \(b\), contains a path from \(a\) to \(b\) if and only if such a path exists in all graphs of \(\mathcal{G}\). Our goal is to compute an efficient representation of \(\mathcal{J}(\mathcal{G})\). In particular, we consider two versions of this problem. In the explicit version we wish to construct the smallest join-reachability graph for \(\mathcal{G}\). In the implicit version we wish to build an efficient data structure (in terms of space and query time) such that we can report fast the set of vertices that reach a query vertex in all graphs of \(\mathcal{G}\). This problem is related to the well-studied reachability problem and is motivated by emerging applications of graph-structured databases and graph algorithms. We consider the construction of join-reachability structures for two graphs and develop techniques that can be applied to both the explicit and the implicit problem. First we present optimal and near-optimal structures for paths and trees. Then, based on these results, we provide efficient structures for planar graphs and general directed graphs.
For the entire collection see [Zbl 1215.68017].
For the entire collection see [Zbl 1215.68017].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C20 | Directed graphs (digraphs), tournaments |
References:
| [1] | Agrawal, R., Borgida, A., Jagadish, H.V.: Efficient management of transitive relationships in large data and knowledge bases. In: SIGMOD 1989: Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, pp. 253–262 (1989) · doi:10.1145/67544.66950 |
| [2] | Aho, A.V., Garey, M.R., Ullman, J.D.: The transitive reduction of a directed graph. SIAM J. Comput. 1(2), 131–137 (1972) · Zbl 0247.05128 · doi:10.1137/0201008 |
| [3] | Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: WWW 2001: Proceedings of the 10th International Conference on World Wide Web, pp. 613–622 (2001) · doi:10.1145/371920.372165 |
| [4] | Georgiadis, L.: Computing frequency dominators and related problems. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 704–715. Springer, Heidelberg (2008) · Zbl 1183.68427 · doi:10.1007/978-3-540-92182-0_62 |
| [5] | Georgiadis, L.: Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs. In: Proc. 37th Int’l. Coll. on Automata, Languages, and Programming, pp. 738–749 (2010) · Zbl 1288.05273 |
| [6] | Georgiadis, L., Nikolopoulos, S.D., Palios, L.: Join-reachability problems in directed graphs. Technical Report arXiv:1012.4938v1 [cs.DS] (2010) · Zbl 1306.05077 |
| [7] | Georgiadis, L., Tarjan, R.E.: Dominator tree verification and vertex-disjoint paths. In: Proc. 16th ACM-SIAM Symp. on Discrete Algorithms, pp. 433–442 (2005) · Zbl 1297.05178 |
| [8] | Kameda, T.: On the vector representation of the reachability in planar directed graphs. Information Processing Letters 3(3), 75–77 (1975) · Zbl 0302.05106 · doi:10.1016/0020-0190(75)90019-8 |
| [9] | Katriel, I., Kutz, M., Skutella, M.: Reachability substitutes for planar digraphs. Technical Report MPI-I-2005-1-002, Max-Planck-Institut Für Informatik (2005) |
| [10] | Talamo, M., Vocca, P.: An efficient data structure for lattice operations. SIAM J. Comput. 28(5), 1783–1805 (1999) · Zbl 0927.06005 · doi:10.1137/S0097539794274404 |
| [11] | Tamassia, R., Tollis, I.G.: Dynamic reachability in planar digraphs with one source and one sink. Theoretical Computer Science 119(2), 331–343 (1993) · Zbl 0830.68105 · doi:10.1016/0304-3975(93)90164-O |
| [12] | Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM 51(6), 993–1024 (2004) · Zbl 1125.68394 · doi:10.1145/1039488.1039493 |
| [13] | Wang, H., He, H., Yang, J., Yu, P.S., Yu, J.X.: Dual labeling: Answering graph reachability queries in constant time. In: ICDE 2006: Proceedings of the 22nd International Conference on Data Engineering, p. 75 (2006) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
