Graph Traversals as Universal Constructions
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Graph Traversals as Universal Constructions
Final published version, 819 KB, PDF document
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 language | English |
---|---|
Title of host publication | 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 |
Editors | Filippo Bonchi, Simon J. Puglisi |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2021 |
Pages | 1-20 |
Article number | 17 |
ISBN (Electronic) | 9783959772013 |
DOIs | |
Publication status | Published - 2021 |
Event | 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 - Tallinn, Estonia Duration: 23 Aug 2021 → 27 Aug 2021 |
Conference
Conference | 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 |
---|---|
Land | Estonia |
By | Tallinn |
Periode | 23/08/2021 → 27/08/2021 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 202 |
ISSN | 1868-8969 |
- Adjunctions, Category theory, Graph traversals, Universal constructions
Research areas
ID: 281985117