Document Open Access Logo

Dynamic Dominators and Low-High Orders in DAGs

Authors Loukas Georgiadis , Konstantinos Giannis, Giuseppe F. Italiano , Aikaterini Karanasiou, Luigi Laura

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.50.pdf
  • Filesize: 0.71 MB
  • 18 pages

Document Identifiers

Author Details

Loukas Georgiadis
  • Department of Computer Science & Engineering, University of Ioannina, Greece
Konstantinos Giannis
  • Department of Computer Science & Engineering, University of Ioannina, Greece
Giuseppe F. Italiano
  • LUISS University, Rome, Italy
Aikaterini Karanasiou
  • Università di Roma "Tor Vergata", Italy
Luigi Laura
  • LUISS University, Rome, Italy

Funding

  • Italiano, Giuseppe F.: Work partially supported by MIUR, the Italian Ministry for Education, University and Research, under PRIN Project AHeAD (Efficient Algorithms for HArnessing Networked Data).

Acknowledgements

We thank the anonymous reviewers for several comments that helped us improve the presentation of our paper.

Cite AsGet BibTex

Loukas Georgiadis, Konstantinos Giannis, Giuseppe F. Italiano, Aikaterini Karanasiou, and Luigi Laura. Dynamic Dominators and Low-High Orders in DAGs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 50:1-50:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.50

Abstract

We consider practical algorithms for maintaining the dominator tree and a low-high order in directed acyclic graphs (DAGs) subject to dynamic operations. Let G be a directed graph with a distinguished start vertex s. The dominator tree D of G is a tree rooted at s, such that a vertex v is an ancestor of a vertex w if and only if all paths from s to w in G include v. The dominator tree is a central tool in program optimization and code generation, and has many applications in other diverse areas including constraint programming, circuit testing, biology, and in algorithms for graph connectivity problems. A low-high order of G is a preorder of D that certifies the correctness of D, and has further applications in connectivity and path-determination problems. We first provide a practical and carefully engineered version of a recent algorithm [ICALP 2017] for maintaining the dominator tree of a DAG through a sequence of edge deletions. The algorithm runs in O(mn) total time and O(m) space, where n is the number of vertices and m is the number of edges before any deletion. In addition, we present a new algorithm that maintains a low-high order of a DAG under edge deletions within the same bounds. Both results extend to the case of reducible graphs (a class that includes DAGs). Furthermore, we present a fully dynamic algorithm for maintaining the dominator tree of a DAG under an intermixed sequence of edge insertions and deletions. Although it does not maintain the O(mn) worst-case bound of the decremental algorithm, our experiments highlight that the fully dynamic algorithm performs very well in practice. Finally, we study the practical efficiency of all our algorithms by conducting an extensive experimental study on real-world and synthetic graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Connectivity
  • dominators
  • low-high orders

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Allesina and A. Bodini. Who dominates whom in the ecosystem? Energy flow bottlenecks and cascading extinctions. Journal of Theoretical Biology, 230(3):351-358, 2004. Google Scholar
  2. S. Alstrup, D. Harel, P. W. Lauridsen, and M. Thorup. Dominators in Linear Time. SIAM Journal on Computing, 28(6):2117-32, 1999. Google Scholar
  3. S. Alstrup and P. W. Lauridsen. A simple dynamic algorithm for maintaining a dominator tree. Technical Report 96-3, Department of Computer Science, University of Copenhagen, 1996. Google Scholar
  4. M. E. Amyeen, W. K. Fuchs, I. Pomeranz, and V. Boppana. Fault Equivalence Identification Using Redundancy Information and Static and Dynamic Extraction. In Proceedings of the 19th IEEE VLSI Test Symposium, March 2001. Google Scholar
  5. S. Baswana, K. Choudhary, and L. Roditty. Fault Tolerant Reachability for Directed Graphs. In Yoram Moses, editor, Distributed Computing, volume 9363 of Lecture Notes in Computer Science, pages 528-543. Springer Berlin Heidelberg, 2015. URL: https://doi.org/10.1007/978-3-662-48653-5_35.
  6. S. Baswana, K. Choudhary, and L. Roditty. Fault Tolerant Reachability Subgraph: Generic and Optimal. In Proc. 48th ACM Symp. on Theory of Computing, pages 509-518, 2016. Google Scholar
  7. M. A. Bender, R. Cole, E. D. Demaine, M. Farach-Colton, and J. Zito. Two Simplified Algorithms for Maintaining Order in a List. In Proc. 10th European Symposium on Algorithms, pages 152-164, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-45749-6_17.
  8. A. L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R. E. Tarjan, and J. R. Westbrook. Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems. SIAM Journal on Computing, 38(4):1533-1573, 2008. Google Scholar
  9. M. D. Carroll and B. G. Ryder. Incremental data flow analysis via dominator and attribute update. In Proc. 15th ACM POPL, pages 274-284, 1988. Google Scholar
  10. S. Cicerone, D. Frigioni, U. Nanni, and F. Pugliese. A uniform approach to semi-dynamic problems on digraphs. Theor. Comput. Sci., 203:69-90, August 1998. Google Scholar
  11. R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451-490, 1991. URL: https://doi.org/10.1145/115372.115320.
  12. P. Dietz and D. Sleator. Two algorithms for maintaining order in a list. In Proc. 19th ACM Symp. on Theory of Computing, pages 365-372, 1987. Google Scholar
  13. David Eppstein, Zvi Galil, and Giuseppe F. Italiano. Dynamic graph algorithms. In Algorithms and Theory of Computation Handbook, 2nd Edition, Vol. 1, pages 9.1-9.28. CRC Press, 2009. Google Scholar
  14. W. Fraczak, L. Georgiadis, A. Miller, and R. E. Tarjan. Finding dominators via disjoint set union. Journal of Discrete Algorithms, 23:2-20, 2013. URL: https://doi.org/10.1016/j.jda.2013.10.003.
  15. H. N. Gabow. The Minset-Poset Approach to Representations of Graph Connectivity. ACM Transactions on Algorithms, 12(2):24:1-24:73, February 2016. URL: https://doi.org/10.1145/2764909.
  16. K. Gargi. A Sparse Algorithm for Predicated Global Value Numbering. SIGPLAN Not., 37(5):45-56, May 2002. URL: https://doi.org/10.1145/543552.512536.
  17. L. Georgiadis. 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, pages 738-749, 2010. Google Scholar
  18. L. Georgiadis. Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph. In Proc. 19th European Symposium on Algorithms, pages 13-24, 2011. Google Scholar
  19. L. Georgiadis, K. Giannis, A. Karanasiou, and L. Laura. Incremental Low-High Orders of Directed Graphs and Applications. In Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi, and Rajeev Raman, editors, 16th International Symposium on Experimental Algorithms (SEA 2017), volume 75 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:21, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SEA.2017.27.
  20. L. Georgiadis, T. D. Hansen, G. F. Italiano, S. Krinninger, and N. Parotsidis. Decremental Data Structures for Connectivity and Dominators in Directed Graphs. In ICALP, pages 42:1-42:15, 2017. Google Scholar
  21. L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis. 2-Edge Connectivity in Directed Graphs. In Proc. 26th ACM-SIAM Symp. on Discrete Algorithms, pages 1988-2005, 2015. Google Scholar
  22. L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis. 2-Vertex Connectivity in Directed Graphs. In Proc. 42nd Int'l. Coll. on Automata, Languages, and Programming, pages 605-616, 2015. Google Scholar
  23. L. Georgiadis, G. F. Italiano, L. Laura, and F. Santaroni. An Experimental Study of Dynamic Dominators. In Proc. 20th European Symposium on Algorithms, pages 491-502, 2012. Full version: CoRR, URL: https://arxiv.org/abs/1604.02711.
  24. L. Georgiadis, G. F. Italiano, and N. Parotsidis. Incremental 2-Edge-Connectivity in Directed Graphs. In ICALP, pages 49:1-49:15, 2016. Google Scholar
  25. L. Georgiadis and R. E. Tarjan. Dominator Tree Certification and Divergent Spanning Trees. ACM Transactions on Algorithms, 12(1):11:1-11:42, November 2015. URL: https://doi.org/10.1145/2764913.
  26. L. Georgiadis and R. E. Tarjan. Addendum to "Dominator Tree Certification and Divergent Spanning Trees". ACM Transactions on Algorithms, 12(4):56:1-56:3, August 2016. URL: https://doi.org/10.1145/2928271.
  27. L. Georgiadis, R. E. Tarjan, and R. F. Werneck. Finding Dominators in Practice. Journal of Graph Algorithms and Applications (JGAA), 10(1):69-94, 2006. Google Scholar
  28. M. Gomez-Rodriguez and B. Schölkopf. Influence Maximization in Continuous Time Diffusion Networks. In 29th International Conference on Machine Learning (ICML), 2012. Google Scholar
  29. Andreas D.M. Gunawan, Bhaskar DasGupta, and Louxin Zhang. A decomposition theorem and two algorithms for reticulation-visible networks. Information and Computation, 252:161-175, 2017. URL: https://doi.org/10.1016/j.ic.2016.11.001.
  30. M. S. Hecht and J. D. Ullman. Characterizations of Reducible Flow Graphs. Journal of the ACM, 21(3):367-375, 1974. Google Scholar
  31. M. Henzinger, S. Krinninger, and V. Loitzenbauer. Finding 2-edge and 2-vertex strongly connected components in quadratic time. In Proc. 42nd Int'l. Coll. on Automata, Languages, and Programming, pages 713-724, 2015. Google Scholar
  32. G. F. Italiano, L. Laura, and F. Santaroni. Finding strong bridges and strong articulation points in linear time. Theoretical Computer Science, 447:74-84, 2012. URL: https://doi.org/10.1016/j.tcs.2011.11.011.
  33. R. Jaberi. Computing the 2-blocks of directed graphs. RAIRO-Theor. Inf. Appl., 49(2):93-119, 2015. URL: https://doi.org/10.1051/ita/2015001.
  34. R. Jaberi. On computing the 2-vertex-connected components of directed graphs. Discrete Applied Mathematics, 204:164-172, 2016. URL: https://doi.org/10.1016/j.dam.2015.10.001.
  35. Jérôme Kunegis. KONECT: the Koblenz network collection. In 22nd International World Wide Web Conference, WWW '13, Rio de Janeiro, Brazil, May 13-17, 2013, Companion Volume, pages 1343-1350, 2013. URL: https://doi.org/10.1145/2487788.2488173.
  36. T. Lengauer and R. E. Tarjan. A Fast Algorithm for Finding Dominators in a Flowgraph. ACM Transactions on Programming Languages and Systems, 1(1):121-41, 1979. Google Scholar
  37. J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.
  38. E. K. Maxwell, G. Back, and N. Ramakrishnan. Diagnosing memory leaks using graph mining on heap dumps. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '10, pages 115-124, 2010. Google Scholar
  39. R. M. McConnell, K. Mehlhorn, S. Näher, and P. Schweitzer. Certifying algorithms. Computer Science Review, 5(2):119-161, 2011. Google Scholar
  40. L. Quesada, P. Van Roy, Y. Deville, and R. Collet. Using Dominators for Solving Constrained Path Problems. In Proc. 8th International Conference on Practical Aspects of Declarative Languages, pages 73-87, 2006. Google Scholar
  41. G. Ramalingam and T. Reps. An incremental algorithm for maintaining the dominator tree of a reducible flowgraph. In POPL, pages 287-296, 1994. Google Scholar
  42. V. C. Sreedhar, G. R. Gao, and Y. Lee. Incremental computation of dominator trees. ACM Transactions on Programming Languages and Systems, 19:239-252, 1997. Google Scholar
  43. R. E. Tarjan. Finding Dominators in Directed Graphs. SIAM Journal on Computing, 3(1):62-89, 1974. Google Scholar
  44. R. E. Tarjan. Testing Flow Graph Reducibility. J. Comput. Syst. Sci., 9(3):355-365, 1974. URL: https://doi.org/10.1016/S0022-0000(74)80049-8.
  45. T. Tholey. Linear time algorithms for two disjoint paths problems on directed acyclic graphs. Theoretical Computer Science, 465:35-48, 2012. URL: https://doi.org/10.1016/j.tcs.2012.09.025.
  46. J. Zhao and S. Zdancewic. Mechanized Verification of Computing Dominators for Formalizing Compilers. In Proc. 2nd International Conference on Certified Programs and Proofs, pages 27-42. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-35308-6_6.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact