Graph Traversals as Universal Constructions
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Graph Traversals as Universal Constructions. / Bhaskar, Siddharth; Kaarsgaard, Robin.
46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021. ed. / Filippo Bonchi; Simon J. Puglisi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. p. 1-20 17 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 202).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Graph Traversals as Universal Constructions
AU - Bhaskar, Siddharth
AU - Kaarsgaard, Robin
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Adjunctions
KW - Category theory
KW - Graph traversals
KW - Universal constructions
UR - http://www.scopus.com/inward/record.url?scp=85115355426&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2021.17
DO - 10.4230/LIPIcs.MFCS.2021.17
M3 - Article in proceedings
AN - SCOPUS:85115355426
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 20
BT - 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
A2 - Bonchi, Filippo
A2 - Puglisi, Simon J.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
Y2 - 23 August 2021 through 27 August 2021
ER -
ID: 281985117