Enumerating m-Length Walks in Directed Graphs with Constant Delay

Adamson, Duncan ORCID: 0000-0003-3343-2435, Gawrychowski, Pawel and Manea, Florin (2024) Enumerating m-Length Walks in Directed Graphs with Constant Delay. [Preprint]

PDF 2401.02163.pdf - Preprint version Download (494kB) | Preview

Abstract

In this paper, we provide a novel enumeration algorithm for the set of all walks of a given length within a directed graph. Our algorithm has worst-case constant delay between outputting succinct representations of such walks, after a preprocessing step requiring linear time relative to the size of the graph. We apply these results to the problem of enumerating succinct representations of the strings of a given length from a prefix-closed regular language (languages accepted by a finite automaton which has final states only).

Item Type:	Preprint
Uncontrolled Keywords:	cs.DS, cs.DS
Divisions:	Faculty of Science and Engineering > School of Physical Sciences
Depositing User:	Symplectic Admin
Date Deposited:	09 Jan 2024 10:42
Last Modified:	26 Mar 2024 05:30
DOI:	10.48550/arxiv.2401.02163
Related URLs:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3177766