Enumerating m-length walks in directed graphs with constant delay

Duncan Adamson; Paweł Gawrychowski; Florin Manea

doi:10.1007/978-3-031-55598-5_3

Enumerating m-length walks in directed graphs with constant delay

Duncan Adamson^*, Paweł Gawrychowski, Florin Manea

^*Corresponding author for this work

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	LATIN 2024 - Theoretical informatics
Subtitle of host publication	16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I
Editors	José A. Soto, Andreas Wiese
Place of Publication	Cham
Publisher	Springer
Pages	35-50
Number of pages	16
ISBN (Electronic)	9783031555985
ISBN (Print)	9783031555978
DOIs	https://doi.org/10.1007/978-3-031-55598-5_3
Publication status	Published - 6 Mar 2024
Event	16th Latin American Symposium on Theoretical Informatics, LATIN 2042 - Puerto Varas, Chile Duration: 18 Mar 2024 → 22 Mar 2024 https://latin2024.cmm.uchile.cl/

Publication series

Name	Lecture notes in computer science
Volume	14578
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th Latin American Symposium on Theoretical Informatics, LATIN 2042
Country/Territory	Chile
City	Puerto Varas
Period	18/03/24 → 22/03/24
Internet address	https://latin2024.cmm.uchile.cl/

Access to Document

10.1007/978-3-031-55598-5_3

Cite this

Adamson, D., Gawrychowski, P., & Manea, F. (2024). Enumerating m-length walks in directed graphs with constant delay. In J. A. Soto, & A. Wiese (Eds.), LATIN 2024 - Theoretical informatics: 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I (pp. 35-50). (Lecture notes in computer science; Vol. 14578). Springer. https://doi.org/10.1007/978-3-031-55598-5_3

@inproceedings{aee2358887034e1a9a49c5df01f1ac87,

title = "Enumerating m-length walks in directed graphs with constant delay",

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

author = "Duncan Adamson and Pawe{\l} Gawrychowski and Florin Manea",

note = "Funding: Duncan Adamson was supported by the Leverhulme Trust via the Leverhulme Centre for Functional Material Design and by DFG Heisenberg-project number 389613931. Florin Manea was supported by DFG Heisenberg-project number 466789228.; 16th Latin American Symposium on Theoretical Informatics, LATIN 2042 ; Conference date: 18-03-2024 Through 22-03-2024",

year = "2024",

month = mar,

day = "6",

doi = "10.1007/978-3-031-55598-5_3",

language = "English",

isbn = "9783031555978",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "35--50",

editor = "Soto, {Jos{\'e} A.} and Andreas Wiese",

booktitle = "LATIN 2024 - Theoretical informatics",

address = "Netherlands",

url = "https://latin2024.cmm.uchile.cl/",

}

Adamson, D, Gawrychowski, P & Manea, F 2024, Enumerating m-length walks in directed graphs with constant delay. in JA Soto & A Wiese (eds), LATIN 2024 - Theoretical informatics: 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I. Lecture notes in computer science, vol. 14578, Springer, Cham, pp. 35-50, 16th Latin American Symposium on Theoretical Informatics, LATIN 2042, Puerto Varas, Chile, 18/03/24. https://doi.org/10.1007/978-3-031-55598-5_3

Enumerating m-length walks in directed graphs with constant delay. / Adamson, Duncan; Gawrychowski, Paweł; Manea, Florin.
LATIN 2024 - Theoretical informatics: 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I. ed. / José A. Soto; Andreas Wiese. Cham: Springer, 2024. p. 35-50 (Lecture notes in computer science; Vol. 14578).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Enumerating m-length walks in directed graphs with constant delay

AU - Adamson, Duncan

AU - Gawrychowski, Paweł

AU - Manea, Florin

N1 - Funding: Duncan Adamson was supported by the Leverhulme Trust via the Leverhulme Centre for Functional Material Design and by DFG Heisenberg-project number 389613931. Florin Manea was supported by DFG Heisenberg-project number 466789228.

PY - 2024/3/6

Y1 - 2024/3/6

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

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

U2 - 10.1007/978-3-031-55598-5_3

DO - 10.1007/978-3-031-55598-5_3

M3 - Conference contribution

AN - SCOPUS:85188745338

SN - 9783031555978

T3 - Lecture notes in computer science

SP - 35

EP - 50

BT - LATIN 2024 - Theoretical informatics

A2 - Soto, José A.

A2 - Wiese, Andreas

PB - Springer

CY - Cham

T2 - 16th Latin American Symposium on Theoretical Informatics, LATIN 2042

Y2 - 18 March 2024 through 22 March 2024