Document Open Access Logo

Graph Traversals as Universal Constructions

Authors Siddharth Bhaskar , Robin Kaarsgaard

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.17.pdf
  • Filesize: 0.79 MB
  • 20 pages

Document Identifiers

Author Details

Siddharth Bhaskar
  • Department of Computer Science, University of Copenhagen, Denmark
Robin Kaarsgaard
  • School of Informatics, University of Edinburgh, UK

Funding

  • Bhaskar, Siddharth: Supported by DFF ∣ Natural Sciences research project 1 fellowship 115554 Cons-Free Recursion Theory.
  • Kaarsgaard, Robin: Supported by DFF ∣ Natural Sciences international postdoctoral fellowship 0131-00025B Landauer Meets von Neumann: Reversibility in Categorical Quantum Semantics.

Acknowledgements

We would like to thank Steve Lindell and Scott Weinstein for inspiring us to study traversals in terms of their predecessor functions, as well as suggesting the characterization of breadth-first traversals in Corollary 27. We also thank Jade Master for discussions relating to this work. We are indebted to the anonymous reviewers for their thorough and detailed comments.

Cite As Get BibTex

Siddharth Bhaskar and Robin Kaarsgaard. Graph Traversals as Universal Constructions. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.17

Abstract

We exploit a decomposition of graph traversals to give a novel characterization of depth-first and breadth-first traversals by means of universal constructions. Specifically, we introduce functors from two different categories of edge-ordered directed graphs into two different categories of transitively closed edge-ordered graphs; one defines the lexicographic depth-first traversal and the other the lexicographic breadth-first traversal. We show that each functor factors as a composition of universal constructions, and that the usual presentation of traversals as linear orders on vertices can be recovered with the addition of an inclusion functor. Finally, we raise the question of to what extent we can recover search algorithms from the categorical description of the traversal they compute.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
  • Theory of computation → Models of computation
Keywords
  • graph traversals
  • adjunctions
  • universal constructions
  • category theory

Metrics

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

Related Versions

References

  1. S. Abramsky. Whither semantics? Theoretical Computer Science, 807:3-14, 2020. Google Scholar
  2. J. Adámek, S. Milius, L. S. Moss, and L. Sousa. Well-pointed coalgebras. Logical Methods in Computer Science, 9(3), 2013. Google Scholar
  3. E. Allender, A. Chauhan, and S. Datta. Depth-first search in directed graphs, revisited. Electronic colloquium on computational complexity, 20(74), 2020. Google Scholar
  4. S. Bhaskar and R. Kaarsgaard. Graph traversals as universal constructions, 2021. URL: http://arxiv.org/abs/2104.14877.
  5. D. Corneil and R. Krueger. A unified view of graph searching. SIAM J. Discrete Math., 22:1259-1276, January 2008. Google Scholar
  6. P. Delatorre and C. P. Kruskal. Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search. Theory of Computing Systems, 34:275-298, 2001. Google Scholar
  7. P. Delatorre and C.P. Kruskal. Fast parallel algorithms for all-sources lexicographic search and path-algebra problems. Journal of Algorithms, 19(1):1-24, 1995. Google Scholar
  8. L. Dixon and A. Kissinger. Open-graphs and monoidal theories. Mathematical Structures in Computer Science, 23(2):308–359, 2013. Google Scholar
  9. J. Kock. Graphs, hypergraphs, and properads. Collectanea mathematica, 67(2):155-190, 2016. Google Scholar
  10. S. Lack and P. Sobociński. Adhesive and quasiadhesive categories. RAIRO-Theoretical Informatics and Applications, 39(3):511-545, 2005. Google Scholar
  11. J. Master. The open algebraic path problem, 2020. URL: http://arxiv.org/abs/2005.06682.
  12. J. Rathke, P. Sobociński, and O. Stephens. Compositional reachability in petri nets. In J. Ouaknine, I. Potapov, and J. Worrell, editors, Reachability Problems, pages 230-243. Springer, 2014. Google Scholar
  13. D. J. Rose and R. E. Tarjan. Algorithmic aspects of vertex elimination. In Proceedings of the Seventh Annual ACM Symposium on Theory of Computing (STOC '75), pages 245-254. ACM, 1975. Google Scholar
  14. T. Wißmann, S. Milius, S. Katsumata, and J. Dubut. A coalgebraic view on reachability. Commentationes Mathematicae Universitatis Carolinae, 60(4):605-638, 2019. Google Scholar
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 About DROPS Imprint Privacy Contact