Enumerating m-length walks in directed graphs with constant delay

Duncan Adamson*, Paweł Gawrychowski, Florin Manea

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish
Title of host publicationLATIN 2024 - Theoretical informatics
Subtitle of host publication16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I
EditorsJosé A. Soto, Andreas Wiese
Place of PublicationCham
PublisherSpringer
Pages35-50
Number of pages16
ISBN (Electronic)9783031555985
ISBN (Print)9783031555978
DOIs
Publication statusPublished - 6 Mar 2024
Event16th Latin American Symposium on Theoretical Informatics, LATIN 2042 - Puerto Varas, Chile
Duration: 18 Mar 202422 Mar 2024

Publication series

NameLecture notes in computer science
Volume14578
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th Latin American Symposium on Theoretical Informatics, LATIN 2042
Country/TerritoryChile
CityPuerto Varas
Period18/03/2422/03/24

Fingerprint

Dive into the research topics of 'Enumerating m-length walks in directed graphs with constant delay'. Together they form a unique fingerprint.

Cite this