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: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3177766 |
Altmetric
Altmetric
