Enumerating m-Length Walks in Directed Graphs with Constant Delay

2024/01/04 by Duncan Adamson, Paweł Gawrychowski, Adamson, Duncan +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2401.02163

openalex publication_date 2024/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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).

Cited by

• Efficiently Finding All Minimal and Shortest Absent Subsequences in a String

Related

• Distinct Shortest Walk Enumeration for RPQs
• Matching walks that are minimal with respect to edge inclusion
• String Matching in (Block) Graphs: A Full Classification by Walk Length
• Finding All Bounded-Length Simple Cycles in a Directed Graph -- Revisited
• Linear-Time Online Algorithm Inferring the Shortest Path from a Walk