Conflict coloring problems: (theory, complexity, algorithm), and application to multi-resolution modeling in structural bioinformatics - 3IA Côte d’Azur – Interdisciplinary Institute for Artificial Intelligence Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2022

Conflict coloring problems: (theory, complexity, algorithm), and application to multi-resolution modeling in structural bioinformatics

Résumé

Given a graph G = (V , E), a color set C(v) for each vertex v ∈ V , a bipartite graph between color sets C(u) and C(v) for every edge uv ∈ E, Conflict Coloring consists in deciding whether there exists a conflict coloring, that is a coloring in which c(u)c(v) is not an edge of the bipartite graph. Conflict Coloring is motivated by high-resolution determination of molecular assemblies. The graph represents the subunits and the interaction between them, the colors are the given conformations, and the edges of the bipartite graphs are the incompatible conformations of two subunits. In this paper, we first establish the complexity dichotomies (polynomial vs NP-complete) for Conflict Coloring and its variants. We provide some experiments in which we build instances of Conflict Coloring associated to Voronoi diagram in the plane, and we then analyse the existences of a solution related to parameters used in our experimental setup.
Fichier principal
Vignette du fichier
CHMN-2022.pdf (1.09 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03666380 , version 1 (12-05-2022)

Identifiants

  • HAL Id : hal-03666380 , version 1

Citer

Frédéric Havet, Dorian Mazauric, Thi Viet Ha Nguyen, Frédéric Cazals. Conflict coloring problems: (theory, complexity, algorithm), and application to multi-resolution modeling in structural bioinformatics. 2022. ⟨hal-03666380⟩
141 Consultations
72 Téléchargements

Partager

Gmail Facebook X LinkedIn More