| Přispěvatelé: |
Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), BQR INPG 'Optimisation du transport de fret par l'utilisation de plateformes logistiques', Rapine, Christophe |
| Popis: |
Given 2 integers a and b, we define an (a,b)-decomposition of a graph G =(V,E) as a partition of E into paths where the length of each path lies between a and b. In this definition paths are requested to be simple but not necessarily elementary. In other words an (a,b)-decomposition corresponds to a partition E1,...,Ek of E with a = 3, we identify 2 classes of graphs, trees and Eulerian graphs, for which the (a,b)-decomposition problem remains polynomial. However we prove that the (3,3)-decomposition problem is NP-complete, even on bipartite graphs. We give some evidence to conjecture that the more general H-decomposition problem into a given family H = H1,...,Hn of connected graphs is NP-complete if and only if all Hi-decomposition problems are NP-complete. |
