Graph Traversals as Universal Constructions

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Siddharth Bhaskar
  • Robin Kaarsgaard

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.

Original languageEnglish
Title of host publication46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
EditorsFilippo Bonchi, Simon J. Puglisi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date2021
Pages1-20
Article number17
ISBN (Electronic)9783959772013
DOIs
Publication statusPublished - 2021
Event46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 - Tallinn, Estonia
Duration: 23 Aug 202127 Aug 2021

Conference

Conference46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
LandEstonia
ByTallinn
Periode23/08/202127/08/2021
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume202
ISSN1868-8969

    Research areas

  • Adjunctions, Category theory, Graph traversals, Universal constructions

ID: 281985117