Готові списки джерел за темами / Graphes paramétrés / Дисертації
Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Graphes paramétrés.

Дисертації з теми "Graphes paramétrés"

Автор: Grafiati
Опубліковано: 4 квітня 2023
Оновлено: 31 липня 2025

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Ознайомтеся з топ-21 дисертацій для дослідження на тему "Graphes paramétrés".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.

1

Sérée, Bastien. "Problèmes d'optimisation des les graphes paramétrés." Electronic Thesis or Diss., Ecole centrale de Nantes, 2022. http://www.theses.fr/2022ECDN0066.

Повний текст джерела
Анотація:
Nous considérons des graphes orientés pondérés dont l’énergie est paramétrée. Nous proposons dans un premier temps un algorithme qui, étant donné un graphe et un de ses sommets, renvoie des arbres, chaque arbre représentant les plus courtschemins depuis la source vers tous les autres sommets du graphe pour une zone particulière de l’espace des paramètres. De plus l’union de ces zones couvre l’espace des paramètres. Nous considérons ensuite l’accessibilité dans les graphes à énergie multidimensionnelle, avec un type de contraintes plus absolues qui imposent que l’énergie reste entre des bornes.
Стилі APA, Harvard, Vancouver, ISO та ін.
2

Diallo, Madiagne. "Réseaux de flots : flots paramétrés et tarification." Versailles-St Quentin en Yvelines, 2003. http://www.theses.fr/2003VERS0030.

Повний текст джерела
Анотація:
My thesis focusses on two applications of network flow problems. We emphasize on networks modelling energy or fluid distribution and telecommunication services. We study two differents aspects:The first aspect consists of the sensitivity analysis of flows in distribution networks. That is the analysis of the effects of one or more capacity variations on the all pairs maximum flow values. Moreover, we evaluate the importance of an edge in the network. Our contributions begin with a correction of the unique method in the literature that dealed with the case of a single capacity variation. We the
Стилі APA, Harvard, Vancouver, ISO та ін.
3

Montealegre, Barba Pedro. "Algorithmes de graphes séquentiels et distribués : algorithmes paramétrés via des cliques maximales potentielles : modèle de diffusion dans une clique congestionnée." Thesis, Orléans, 2017. http://www.theses.fr/2017ORLE2001/document.

Повний текст джерела
Анотація:
Cette thèse porte sur des aspects structuraux et algorithmiques des graphes. Elle est divisée en deux parties, qui comportent deux études différentes : une partie sur des algorithmes centralisés-séquentiels, et une autre sur des algorithmes distribués. Dans la première partie, on étudie des aspects algorithmiques de deux structures de graphes appelés séparateurs minimaux et cliques maximales potentielles. Ces deux objets sont au coeur d'un méta-théorème dû à Fomin, Todinca and Villanger (SIAM J. Comput. 2015), qui affirme qu'une grande famille des problèmes d'optimisation peut être résolue en
Стилі APA, Harvard, Vancouver, ISO та ін.
4

Daligault, Jean. "Techniques combinatoires pour les algorithmes paramétrés et les noyaux, avec applications aux problèmes de multicoupe." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00804206.

Повний текст джерела
Анотація:
Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec
Стилі APA, Harvard, Vancouver, ISO та ін.
5

Cochefert, Manfred. "Algorithmes exacts et exponentiels pour les problèmes NP-difficiles sur les graphes et hypergraphes." Thesis, Université de Lorraine, 2014. http://www.theses.fr/2014LORR0336/document.

Повний текст джерела
Анотація:
Dans cette thèse, nous nous intéressons à la résolution exacte de problèmes NP-difficiles sur les graphes et les hypergraphes. Les problèmes que nous étudions regroupent dans un premier temps des variantes du problème classique du nombre chromatique. Les variantes de ce problème se distinguent par la difficulté introduite par les relations entre les classes de couleurs, ou la difficulté de reconnaissance des classes de couleurs elles-mêmes. Puis nous ferons le lien avec les problèmes de transversaux sur les hypergraphes. Plus particulièrement, il s’agira de s’intéresser à l’énumération de tran
Стилі APA, Harvard, Vancouver, ISO та ін.
6

Cochefert, Manfred. "Algorithmes exacts et exponentiels pour les problèmes NP-difficiles sur les graphes et hypergraphes." Electronic Thesis or Diss., Université de Lorraine, 2014. http://www.theses.fr/2014LORR0336.

Повний текст джерела
Анотація:
Dans cette thèse, nous nous intéressons à la résolution exacte de problèmes NP-difficiles sur les graphes et les hypergraphes. Les problèmes que nous étudions regroupent dans un premier temps des variantes du problème classique du nombre chromatique. Les variantes de ce problème se distinguent par la difficulté introduite par les relations entre les classes de couleurs, ou la difficulté de reconnaissance des classes de couleurs elles-mêmes. Puis nous ferons le lien avec les problèmes de transversaux sur les hypergraphes. Plus particulièrement, il s’agira de s’intéresser à l’énumération de tran
Стилі APA, Harvard, Vancouver, ISO та ін.
7

Fradin, Julien. "Graphes complexes en biologie : problèmes, algorithmes et évaluations." Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4093/document.

Повний текст джерела
Анотація:
Afin de mieux comprendre le fonctionnement d'un système biologique, il est nécessaire d'étudier les différentes entités qui le composent. Pour cela, on peut modéliser ces interactions biologiques sous la forme de graphes. Pour certains de ces graphes, les sommets sont colorés afin d'apporter une information supplémentaire sur la couleur qui leur est associée. Dans ce cadre, une problématique courante consiste à y rechercher un sous-graphe d'intérêt appelé motif. Dans la première partie de ce manuscrit, on présente un état de l'art d'un point de vue algorithmique sur le problème GRAPH MOTIF, qu
Стилі APA, Harvard, Vancouver, ISO та ін.
8

Watrigant, Rémi. "Approximation et complexité paramétrée de problèmes d’optimisation dans les graphes : partitions et sous-graphes." Thesis, Montpellier 2, 2014. http://www.theses.fr/2014MON20100/document.

Повний текст джерела
Анотація:
La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retou
Стилі APA, Harvard, Vancouver, ISO та ін.
9

Chopin, Morgan. "Problèmes d'optimisation avec propagation dans les graphes : complexité paramétrée et approximation." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00933769.

Повний текст джерела
Анотація:
Dans cette thèse, nous étudions la complexité algorithmique de problèmes d'optimisation impliquant un processus de diffusion dans un graphe. Plus précisément, nous nous intéressons tout d'abord au problème de sélection d'un ensemble cible. Ce problème consiste à trouver le plus petit ensemble de sommets d'un graphe à "activer" au départ tel que tous les autres sommets soient activés après un nombre fini d'étapes de propagation. Si nous modifions ce processus en permettant de "protéger" un sommet à chaque étape, nous obtenons le problème du pompier dont le but est de minimiser le nombre total d
Стилі APA, Harvard, Vancouver, ISO та ін.
10

Bouvier, Tom. "Graphes et décompositions." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0341/document.

Повний текст джерела
Анотація:
Dans cette thèse, nous étudions diverses largeurs de graphes autour de la largeur arborescente ainsi que de la largeur de clique. Nous commençons avec une étude comparative entre la largeur arborescente d’un graphe et la largeur de clique du graphe d’incidence associé, de laquelle nous extrayons des résultats algorithmiques encourageants. Puis nous présentons quelques propriétés structurelles liées à la largeur arborescente spéciale, largeur relativement récente qui est à mi-chemin entre les deux largeurs précédentes. Enfin nous nous intéressons à une notion plus générale connue sous le nom de
Стилі APA, Harvard, Vancouver, ISO та ін.
11

Magos, Rivera Miguel. "Sur la modélisation des systèmes dynamiques à topologie variable : une formulation Hamiltonienne à ports paramétrée." Lyon 1, 2005. http://www.theses.fr/2005LYO10016.

Повний текст джерела
Анотація:
Dans cette thèse, nous nous intéressons à la modélisation pour la commande des systèmes physiques à topologie variable. La modélisation du système physique non commandé, est effectuée par une formulation qui conserve explicitement la représentation de l’interconnexion et l’énergie, ce qui permettra l’étude des systèmes non-réguliers par une approche modulaire basée sur le concept de l’énergie. Le principal objectif est alors de représenter de manière structurée toutes les configurations du système, en terme de comportement physiquement possible. Les résultats présentés dans ce mémoire ont pour
Стилі APA, Harvard, Vancouver, ISO та ін.
12

Oijid, Nacim. "Complexité des jeux positionnels sur les graphes." Electronic Thesis or Diss., Lyon 1, 2024. http://www.theses.fr/2024LYO10113.

Повний текст джерела
Анотація:
Cette thèse traite de la complexité des jeux positionnels, c'est-à-dire des jeux dans lesquels deux joueurs prennent à tour de rôle les sommets libres d'un hypergraphe. Dans la convention la plus célèbre, Maker-Breaker, Maker gagne s'il parvient à prendre tous les sommets d'une hyperarête, sinon Breaker gagne. Dans ces jeux, il existe toujours un joueur qui a une stratégie gagnante, et nous étudions ici la complexité algorithmique de déterminer de quel joueur il s'agit, dans différentes conventions et sur différentes structures. Ce modèle de jeu est très général, et dans les études les plus ré
Стилі APA, Harvard, Vancouver, ISO та ін.
13

Garnero, Valentin. "(Méta)-noyaux constructifs et linéaires dans les graphes peu denses." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT328/document.

Повний текст джерела
Анотація:
En algorithmique et en complexité, la plus grande part de la recherche se base sur l’hypothèse que P ≠ NP (Polynomial time et Non deterministic Polynomial time), c'est-à-dire qu'il existe des problèmes dont la solution peut être vérifiée mais non construite en temps polynomial. Si cette hypothèse est admise, de nombreux problèmes naturels ne sont pas dans P (c'est-à-dire, n'admettent pas d'algorithme efficace), ce qui a conduit au développement de nombreuses branches de l'algorithmique. L'une d'elles est la complexité paramétrée. Elle propose des algorithmes exacts, dont l'analyse est faite en
Стилі APA, Harvard, Vancouver, ISO та ін.
14

Chapelle, Mathieu. "Décompositions de graphes : quelques limites et obstructions." Phd thesis, Université d'Orléans, 2011. http://tel.archives-ouvertes.fr/tel-00659666.

Повний текст джерела
Анотація:
Les décompositions de graphes, lorsqu'elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d'obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d'obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme
Стилі APA, Harvard, Vancouver, ISO та ін.
15

Déprés, Hugues. "Twin-width : lower bounds and approximation algorithms." Electronic Thesis or Diss., Lyon, École normale supérieure, 2024. http://www.theses.fr/2024ENSL0011.

Повний текст джерела
Анотація:
Cette thèse porte sur l'étude de nouvelles décomposition de graphes, notamment la twin-width qui est un nouveau paramètre permettant de mesurer la complexité d'un graphe, défini en 2020 par Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant et Édouard Bonnet. C’est un paramètre qui s’est révélé être important dans la compréhension de la structure des graphes et de leurs algorithmes. Dans cette thèse, on montre que, décider si la twin-width d’un graphe est au plus 4, est un problème NP-complet. On réussit en effet à contrôler suffisamment la séquence de contraction pour simuler un circuit booléen.
Стилі APA, Harvard, Vancouver, ISO та ін.
16

Gastineau, Nicolas. "Partitionnement, recouvrement et colorabilité dans les graphes." Thesis, Dijon, 2014. http://www.theses.fr/2014DIJOS014/document.

Повний текст джерела
Анотація:
Nos recherches traitent de coloration de graphes avec des contraintes de distance (coloration de packing) ou des contraintes sur le voisinage (coloration de Grundy). Soit S={si| i in N*} une série croissante d’entiers. Une S -coloration de packing est une coloration propre de sommets telle que tout ensemble coloré i est un si-packing (un ensemble où tous les sommets sont à distance mutuelle supérieure à si). Un graphe G est (s1,... ,sk)-colorable si il existe une S -coloration de packing de G avec les couleurs 1, ...,,k. Une coloration de Grundy est une coloration propre de sommets telle que p
Стилі APA, Harvard, Vancouver, ISO та ін.
17

Perez, Anthony. "Algorithmes de noyau pour des problèmes d'édition de graphes et autres structures." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00660089.

Повний текст джерела
Анотація:
Dans le cadre de cette thèse, nous considérons la complexité paramétrée de problèmes NP- complets. Plus précisément, nous nous intéressons à l'existence d'algorithmes de noyau polynomiaux pour des problèmes d'édition de graphes et de relations. Nous introduisons en particulier la notion de branches, qui permet d'obtenir des algorithmes polynomiaux pour des problèmes d'édition de graphes lorsque la classe de graphes cible respecte une décomposition d'adjacence. Cette technique nous permet ainsi d'élaborer les premiers algorithmes de noyaux polynomiaux pour les problèmes CLOSEST 3-LEAF POWER, CO
Стилі APA, Harvard, Vancouver, ISO та ін.
18

Rinaudo, Philippe. "Algorithmique de l'alignement structure-séquence d'ARN : une approche générale et paramétrée." Phd thesis, Université Paris Sud - Paris XI, 2012. http://tel.archives-ouvertes.fr/tel-00847745.

Повний текст джерела
Анотація:
L'alignement de macromolécules biologiques comme les protéines, l'ADN ou encore l'ARN est une problématique biologique et bio-informatique qui a pour but de révéler une partie des mystères du fonctionnement des cellules, constituants des êtres vivants. Les ARN non-codant sont des macromolécules intervenant dans le métabolisme de tout être vivant et les deux problématiques majeurs les concernant sont: la prédiction de leur structure pour mieux comprendre leur fonctionnement et leur détection dans des bases de données ou des génomes. L'une des approches: l'alignement structure-séquence d'ARN, ré
Стилі APA, Harvard, Vancouver, ISO та ін.
19

Bergé, Pierre. "Algorithmes pour voyager sur un graphe contenant des blocages." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS480.

Повний текст джерела
Анотація:
Nous étudions des problèmes NP-difficiles portant sur les graphes contenant des blocages.Nous traitons les problèmes de coupes du point de vue de la complexité paramétrée. La taille p de la coupe est le paramètre. Étant donné un ensemble de sources {s1,...,sk} et une cible t, nous proposons un algorithme qui construit une coupe de taille au plus p séparant au moins r sources de t. Nous nommons ce problème NP-complet Partial One-Target Cut. Notre algorithme est FPT. Nous prouvons également que la variante de Partial One-Target Cut, où la coupe est composée de noeuds, est W[1]-difficile. Notre s
Стилі APA, Harvard, Vancouver, ISO та ін.
20

Khosravian, Ghadikolaei Mehdi. "Extension of NP Optimization Problems." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED064.

Повний текст джерела
Анотація:
Le problème de la détermination de la qualité d’une solution partielle se pose dans la majeure partie des approches algorithmiques cherchant à calculer progressivement une solution globale. L’élagage des arbres de recherche, la preuve de garanties d’approximation et l’efficacité des stratégies d’énumération sont des approches algorithmiques qui exigent souvent un moyen approprié de décider si une solution partielle donnée est un bon candidat pour l’étendre à une solution globale de bonne qualité. Dans cette thèse, nous étudions un type particulier de problèmes d’optimisation, appelés problèmes
Стилі APA, Harvard, Vancouver, ISO та ін.
21

Majumdar, Anirban. "Verification and synthesis of parameterized concurrent systems." Electronic Thesis or Diss., université Paris-Saclay, 2021. http://www.theses.fr/2021UPASG059.

Повний текст джерела
Анотація:
Cette thèse se situe au croisement de la vérification et de la synthèse des systèmes concurrents paramétrés. Le problème de la vérification de modèles paramétrés demande si un système satisfait une spécification donnée indépendamment du nombre de ses composants, alors que la synthèse vise la conception de protocoles pour ses composants afin que la spécification soit satisfaite.Nous étudions un modèle paramétré de réseaux où les processus sont distribués sur un graphe non orienté; ils exécutent le même protocole et communiquent par des diffusions sélectives de messages. Le problème de couvertur
Стилі APA, Harvard, Vancouver, ISO та ін.
Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!

До бібліографії