1 Search Results for "Kaarsgaard, Robin"

Document
DOI: 10.4230/LIPIcs.MFCS.2021.17
Graph Traversals as Universal Constructions

Authors: Siddharth Bhaskar and Robin Kaarsgaard

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

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.
Cite as

Siddharth Bhaskar and Robin Kaarsgaard. Graph Traversals as Universal Constructions. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.MFCS.2021.17,
  author =	{Bhaskar, Siddharth and Kaarsgaard, Robin},
  title =	{{Graph Traversals as Universal Constructions}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.17},
  URN =		{urn:nbn:de:0030-drops-144573},
  doi =		{10.4230/LIPIcs.MFCS.2021.17},
  annote =	{Keywords: graph traversals, adjunctions, universal constructions, category theory}
}
  • Refine by Author
  • 1 Bhaskar, Siddharth
  • 1 Kaarsgaard, Robin

  • Refine by Classification
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 1 adjunctions
  • 1 category theory
  • 1 graph traversals
  • 1 universal constructions

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact