Graph Traversals as Universal Constructions

Siddharth Bhaskar, Robin Kaarsgaard

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

5 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
EditorsFilippo Bonchi, Simon J. Puglisi
PublisherSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Publication date2021
Pages17:1-17:20
Article number17
ISBN (Electronic)9783959772013
DOIs
Publication statusPublished - 2021
Externally publishedYes
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
Country/TerritoryEstonia
CityTallinn
Period23/08/202127/08/2021
SeriesLeibniz International Proceedings in Informatics
Volume202
ISSN1868-8969

Keywords

  • Adjunctions
  • Category theory
  • Graph traversals
  • Universal constructions

Fingerprint

Dive into the research topics of 'Graph Traversals as Universal Constructions'. Together they form a unique fingerprint.

Cite this