Skip to main content

Low memory graph traversal

Resource type
Thesis type
(Thesis) M.Sc.
Date created
We provide two traversal algorithms. First, we demonstrate that there exists a local orientation for any anonymous graph G, provided that G is not a star graph, and G does not have any induced subgraph that is isomorphic to a path on four vertices. We show that it is possible to periodically traverse G with period at most 2n - 2; this matches the lower bound for the period for general graphs. Next, we provide a traversal for labelled graphs given that they satisfy two properties, which we define. The properties that we define and use are inspired by the properties of geometric planar graphs.
Copyright statement
Copyright is held by the author.
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Stacho, Ladislav
Member of collection
Download file Size
etd6191_SBassett.pdf 825.37 KB

Views & downloads - as of June 2023

Views: 0
Downloads: 0