Survey of Results on the ModPath and ModCycle Problems

Amarilli, Antoine

Document type :

Pré-publication ou Document de travail

Title :

Survey of Results on the ModPath and ModCycle Problems

Author(s) :

Amarilli, Antoine [Auteur]
Linking Dynamic Data [LINKS]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]

Publication date :

2024-09-01

HAL domain(s) :

Informatique [cs]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Comment :

11 pages. Unpublished note surveying existing work

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Files

2409.00770
Open access
Access the document

Survey of Results on the ModPath and ... BibTeX CSV Excel RIS

Files

Survey of Results on the ModPath and ...

BibTeX

CSV

Excel

RIS