Edge-Minimum Walk of Modular Length in Polynomial Time

Antoine Amarilli, Benoît Groz, Nicole Wein · 2024

Read Edge-Minimum Walk of Modular Length in Polynomial Time by Antoine Amarilli, Benoît Groz, Nicole Wein (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01614.txt.

Introduction

Antoine Amarilli, Benoit Groz, and Nicole Wein study a graph problem in a 2024 computer science paper. They seek a walk in a directed graph whose length fits a modular rule, such as a remainder when divided by a fixed number, while using as few distinct edges as possible.

Their main result is an efficient algorithm when the remainder and modulus are constants. The proof method also yields an algorithm for a broader network design problem, where links between endpoint pairs must meet modular length rules. That algorithm stays efficient when the number of pairs and the rules are constant.

Catalog record

CREATORAntoine Amarilli, Benoît Groz, Nicole Wein
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE160 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-01614

Browse the full library · About the Tower of Babel