Survey of Results on the ModPath and ModCycle Problems

Amarilli, Antoine

Type de document :

Pré-publication ou Document de travail

Titre :

Survey of Results on the ModPath and ModCycle Problems

Auteur(s) :

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

Date de publication :

2024-09-01

Discipline(s) HAL :

Informatique [cs]

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Commentaire :

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

Fichiers

2409.00770
Accès libre
Accéder au document

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

Fichiers

Survey of Results on the ModPath and ...

BibTeX

CSV

Excel

RIS