## 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 | |

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 |

### 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 |

## Fingerprint

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