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
| CREATOR | Antoine Amarilli, Benoît Groz, Nicole Wein |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 160 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-01614