Graph Traversals as Universal Constructions

Siddharth Bhaskar, Robin Kaarsgaard

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer 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.
OriginalsprogEngelsk
TitelProceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
RedaktørerFilippo Bonchi, Simon J. Puglisi
ForlagSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Publikationsdato2021
Sider17:1-17:20
Artikelnummer17
ISBN (Elektronisk)9783959772013
DOI
StatusUdgivet - 2021
Udgivet eksterntJa
Begivenhed46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 - Tallinn, Estland
Varighed: 23. aug. 202127. aug. 2021

Konference

Konference46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
Land/OmrådeEstland
ByTallinn
Periode23/08/202127/08/2021
NavnLeibniz International Proceedings in Informatics
Vol/bind202
ISSN1868-8969

Fingeraftryk

Dyk ned i forskningsemnerne om 'Graph Traversals as Universal Constructions'. Sammen danner de et unikt fingeraftryk.

Citationsformater