Survey of Results on the ModPath and ModCycle Problems
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914932118781952 |
|---|---|
| author | Amarilli, Antoine |
| author_facet | Amarilli, Antoine |
| contents | This note summarizes the state of what is known about the tractability of the problem ModPath, which asks if an input undirected graph contains a simple st-path whose length satisfies modulo constraints. We also consider the problem ModCycle, which asks for the existence of a simple cycle subject to such constraints. We also discuss the status of these problems on directed graphs, and on restricted classes of graphs. We explain connections to the problem variant asking for a constant vertex-disjoint number of such paths or cycles, and discuss links to other related work. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_00770 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Survey of Results on the ModPath and ModCycle Problems Amarilli, Antoine Data Structures and Algorithms This note summarizes the state of what is known about the tractability of the problem ModPath, which asks if an input undirected graph contains a simple st-path whose length satisfies modulo constraints. We also consider the problem ModCycle, which asks for the existence of a simple cycle subject to such constraints. We also discuss the status of these problems on directed graphs, and on restricted classes of graphs. We explain connections to the problem variant asking for a constant vertex-disjoint number of such paths or cycles, and discuss links to other related work. |
| title | Survey of Results on the ModPath and ModCycle Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.00770 |