New randomized strategies for the color coding algorithm - Recherche opérationnelle des Systèmes de Production Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

New randomized strategies for the color coding algorithm

Résumé

The color coding technique is used to solve subgraph isomorphism problems, in particular path problems. One color among C is randomly assigned to each vertex of the graph and if distinct colors are given to the vertices of the desired subgraph, it can be found efficiently by dynamic programming. These two phases are repeated until the subgraph is found with a high probability, which can require a large number of iterations. We propose new coloring strategies that take advantage of the graph structure to increase this probability and thus reduce the number of iterations. They provide a guaranteed improvement over the original color coding technique based on a particular structural parameter related to the bandwidth. When this parameter is smaller than the number C of colors, we prove that only C calls to the dynamic program are needed to find the subgraph.
Fichier principal
Vignette du fichier
1270_paper.pdf (435.23 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03058251 , version 1 (11-12-2020)

Identifiants

  • HAL Id : hal-03058251 , version 1

Citer

Lucie Pansart, Hadrien Cambazard, Nicolas Catusse. New randomized strategies for the color coding algorithm. 24th European Conference on Artificial Intelligence, Aug 2020, Santiago de Compostela, Spain. ⟨hal-03058251⟩
46 Consultations
452 Téléchargements

Partager

Gmail Facebook X LinkedIn More