@inproceedings{bb0ee740e887499fadfb8dc2729bf5e6,

title = "Graph Traversals as Universal Constructions",

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.",

keywords = "Adjunctions, Category theory, Graph traversals, Universal constructions",

author = "Siddharth Bhaskar and Robin Kaarsgaard",

year = "2021",

doi = "10.4230/LIPICS.MFCS.2021.17",

language = "English",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik",

pages = "17:1--17:20",

editor = "Filippo Bonchi and Puglisi, {Simon J.}",

booktitle = "Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)",

note = "46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 ; Conference date: 23-08-2021 Through 27-08-2021",

}