Дисертації з теми "Graphes paramétrés"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-17 дисертацій для дослідження на тему "Graphes paramétrés".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
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.
Повний текст джерелаWe are considering weighted oriented graphs with parametrized energy. Firstly we propose an algorithm that, given a graph and one of its vertices, returns trees, every tree representing shortest-paths from the source to every other vertex for a particular zone of the parameter space. Moreover, union of these zones is a covering of the parameter space. Then we consider reachability in graphs with multi-dimensional energy, with stricter constraints that enforce the energy to stay between bounds. We prove decidabilty and complexity of this problem regardless of the dimension and the number of parameters when parameters take integer values. We alsoprove the undecidability of this problem when there is at least one parameter and the dimension is at least two. Finally we study paritygames on parametrized graphs with one and two players whose objective is the conjunction of a qualitative condition on the parity andquantitative one : energy must stay positive. We show the decidability and prove bounds on the complexity of the problem of searchinga winning strategy in both cases with one and two players
Diallo, Madiagne. "Réseaux de flots : flots paramétrés et tarification." Versailles-St Quentin en Yvelines, 2003. http://www.theses.fr/2003VERS0030.
Повний текст джерелаLa thèse se focalise sur des applications des problèmes de flots dans des réseaux modélisant, d'une part des réseaux de distribution de fluide ou d'énergie et d'autre part des réseaux de télécommunication. Nous nous sommes intéressés à deux aspects :Le premier aspect consiste en une analyse de sensibilité des flots sur les réseaux de distribution, c'est à dire, l'étude de l'impact de la variation de la capacité d'une ou de plusieurs arêtes sur l'ensemble des valeurs de flot maximum entre toutes les paires de sommets du réseau. En outre, nous nous sommes intéressés à la rentabilité d'une arête donnée dans un réseau. Nous avons d'abord apporté des corrections à l'unique méthode qui existait dans le cas d'une capacité d'arête qui varie et nous avons proposé des algorithmes simples et efficaces pour résoudre le cas de plusieurs capacités qui varient. Nos méthodes sont basées sur les arbres de coupes de Gomory et Hu. 'Etant donné un réseau non orienté ayant capacités qui peuvent varier avec des paramètres lambda_1,\lambda_2, \lambda_3, \ldots \lambda_k, nous avons montré que 2^k calculs d'un arbre de coupes de Gomory et Hu étaient suffisants pour déterminer les valeurs de flot maximum entre toutes les paires de sommets dans le réseau. En ce qui concerne le problème de la rentabilité d'un lien, nous avons montré que juste 2 calculs d'un arbre de coupes de Gomory et Hu suffisaient pour déterminer l'ensemble des paires de sommets pour lesquelles tout flot maximum sature le lien cible. Le second aspect concerne l'allocation de ressources dans un réseau de télécommunication pour la satisfaction de requêtes d'utilisateurs. Pour ce faire, nous avons étudié ce problème par le biais de la tarification pour gérer la congestion tout en tenant compte du comportement des utilisateurs et de la volonté de profit del'opérateur. Nous avons utilisé une approche bi-niveaux pour résoudre le problème. Avec la méthode du Lagragien augmenté, nous résolvons le problème d'allocation de ressources en associant les multiplicateurs de Lagrange aux prix sur les liens du réseaux. Nous utilisons ensuite les conditions d'optimalité de Karush-Kuhn-Tucker pour vérifier si les ultiplicateurs (prix) sont uniques ou pas. Au cas de non unicité nous montrons comment on peut résoudre un deuxième problème d'optimisation sur ces multiplicateurs (prix) afin d'améliorer le revenu sur le réseau
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.
Повний текст джерелаThis thesis is about structural and algorithmic aspects of graphs. It is divided in two parts, which are about two different studies: one part is about centralized-sequential algorithms, and the other part is about distributed algorithms. In the first part of the thesis we study algorithmic applications of two graph structures called minimal separators and potential maximal cliques. These two objects are in the core of a meta-theorem due to Fomin, Todinca and Villanger (SIAM J. Comput. 2015), which states that a large family of graph optimization problems can be solved in polynomial time, when the input is restricted to the family of graphs with polynomially many minimal separators. The contribution of this part of the thesis is to extend the meta-theorem of Fomin et al. in two ways. On one hand, we adapt it to be valid into a larger family of problems. On the other hand, we extend it into a parameterized version, for several graph parameters. In the second part of this thesis we study the broadcast congested clique model. In this model, the nodes of a graph communicate in synchronous rounds, broadcasting a message of small size visible to every other node. The goal is to design protocols that recognize graph classes minimizing the number of rounds and the message sizes. The contribution of this part is to explore the role of randomness on this model, and provide protocols for the recognition and reconstruction of some graph classes
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.
Повний текст джерела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.
Повний текст джерелаIn this thesis, we are interested in the exact computation of np-hard problems on graphs and hypergraphs. Firstly, we study several variants of colorings. Those variants appear harder than the famous chromatic number problem, by adding difficulty in recognizing the color classes, or more often by introducing various relationships between them. Then we link to problems of transversals in hypergraphs. More precisely, we are interested in enumerating minimal transversals in bounded ranked hypergraphs. Besides the exact computation, we are also interested in fixed parameter tractability. For this area, we study two optimization versions of the famous square root of graphs problem. Finally, we will be interested in solving other problems of graphs related to colorings, or in order to compare efficiencies of algorithms depending on the memory space available. In this thesis, we will apply most of major techniques in designing exact exponential algorithms. The main techniques we use are dynamic programming, inclusion-exclusion, branching, or measure and conquer
Fradin, Julien. "Graphes complexes en biologie : problèmes, algorithmes et évaluations." Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4093/document.
Повний текст джерелаLn order to better understand how a biological system works, it is necessary to study the interactions between the different entities that compose it. To this aim, these biological interactions can be modelled in the form of graphs. ln some of these graphs, the vertices are colored in order to provide additional information on the entity which is associated with them. ln this context, a common subproblem consists in searching for a subgraph of interest, called a motif, in these graphs. ln the first part of this manuscript, we present a state of the art from an algorithmical point of view of the GRAPH MOTIF problem, which consists in searching for so-called functional motifs in vertex-colored graphs. The modeling of biological systems in graphs form can also be applied in mass spectrometry. Thus, we introduce the MAXIMUM COLORFUL ARBORESCENCE problem (MCA) in order to de novo determine the molecular formula of unknown metabolites. ln the second part of this manuscript, we carry out an algorithmic study of the MCA problem. While MCA is algorithmically difficult to solve even in very constrained graph classes, our modeling allows us to obtain new approximation algorithms in these same classes, as well as to determine a new graph class in which MCA is solved in polynomial time. Parameterized complexity results for this problem are also shown, which are then compared to those in the literature on instances from biological data
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.
Повний текст джерелаThe theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms
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.
Повний текст джерелаBouvier, Tom. "Graphes et décompositions." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0341/document.
Повний текст джерелаIn this thesis, we study some width parameters on graphs, beyond tree-width and clique-width. Our first investigation is a comparative study between the tree-width of a graph and the clique-width of the associated incidence graph, from which we extract some strong algorithmic results. Then we present a few structural properties over a recently defined width called special tree-width and which takes its definition through both tree-width and clique-width. Finally, we end our journey with a more general notion named sub-modular partition fonction and which encompass both “classic” and special tree-widths, path-width, branch-width, linear-width, cut-width and carvingwidth among others. So, we introduce a fixed parameter tractable algorithm computing those widths parameters and thus we generalize a number of results specific to each of them
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.
Повний текст джерелаGarnero, Valentin. "(Méta)-noyaux constructifs et linéaires dans les graphes peu denses." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT328/document.
Повний текст джерелаIn the fields of Algorithmic and Complexity, a large area of research is based on the assumption that P ≠ NP(Polynomial time and Non deterministic Polynomial time), which means that there are problems for which a solution can be verified but not constructed in polynomial time. Many natural problems are not in P, which means, that they have no efficient algorithm. In order to tackle such problems, many different branches of Algorithmic have been developed. One of them is called Parametric Complexity. It consists in developing exact algorithms whose complexity is measured as a function of the size of the instance and of a parameter. Such a parameter allows a more precise analysis of the complexity. In this context, an algorithm will be considered to be efficient if it is fixed parameter tractable (fpt), that is, if it has a complexity which is exponential in the parameter and polynomial in the size of the instance. Problems that can be solved by such an algorithm form the FPT class.Kernelisation is a technical that produces fpt algorithms, among others. It can be viewed as a preprocessing of the instance, with a guarantee on the compression of the data. More formally, a kernelisation is a polynomial reduction from a problem to itself, with the additional constraint that the size of the kernel, the reduced instance, is bounded by a function of the parameter. In order to obtain an fpt algorithm, it is sufficient to solve the problem in the reduced instance, by brute-force for example (which has exponential complexity, in the parameter). Hence, the existence of a kernelisiation implies the existence of an fpt algorithm. It holds that the converse is true also. Nevertheless, the existence of an efficient fpt algorithm does not imply a small kernel, meaning a kernel with a linear or polynomial size. Under certain hypotheses, it can be proved that some problems can not have a kernel (that is, are not in FPT) and that some problems in FPT do not have a polynomial kernel.One of the main results in the field of Kernelisation is the construction of a linear kernel for the Dominating Set problem on planar graphs, by Alber, Fellows and Niedermeier.To begin with, the region decomposition method proposed by Alber, Fellows and Niedermeier has been reused many times to develop kernels for variants of Dominating Set on planar graphs. Nevertheless, this method had quite a few inaccuracies, which has invalidated the proofs. In the first part of our thesis, we present a more thorough version of this method and we illustrate it with two examples: Red Blue Dominating Set and Total Dominating Set.Next, the method has been generalised to larger classes of graphs (bounded genus, minor-free, topological-minor-free), and to larger families of problems. These meta-results prove the existence of a linear or polynomial kernel for all problems verifying some generic conditions, on a class of sparse graphs. As a price of generality, the proofs do not provide constructive algorithms and the bound on the size of the kernel is not explicit. In the second part of our thesis, we make a first step to constructive meta-results. We propose a framework to build linear kernels based on principles of dynamic programming and a meta-result of Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh and Thilikos
Chapelle, Mathieu. "Décompositions de graphes : quelques limites et obstructions." Phd thesis, Université d'Orléans, 2011. http://tel.archives-ouvertes.fr/tel-00659666.
Повний текст джерелаGastineau, Nicolas. "Partitionnement, recouvrement et colorabilité dans les graphes." Thesis, Dijon, 2014. http://www.theses.fr/2014DIJOS014/document.
Повний текст джерелаOur research are about graph coloring with distance constraints (packing coloring) or neighborhood constraints (Grundy coloring). Let S={si| i in N*} be a non decreasing sequence of integers. An S-packing coloring is a proper coloring such that every set of color i is an si-packing (a set of vertices at pairwise distance greater than si). A graph G is (s1,... ,sk)-colorable if there exists a packing coloring of G with colors 1,... ,k. A Grundy coloring is a proper vertex coloring such that for every vertex of color i, u is adjacent to a vertex of color j, for each ji. These results allow us to determine S-packing coloring of these lattices for several sequences of integers. We examine a class of graph that has never been studied for S-packing coloring: the subcubic graphs. We determine that every subcubic graph is (1,2,2,2,2,2,2)-colorable and (1,1,2,2,3)-colorable. Few results are proven about some subclasses. Finally, we study the Grundy number of regular graphs. We determine a characterization of the cubic graphs with Grundy number 4. Moreover, we prove that every r-regular graph without induced square has Grundy number r+1, for r<5
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.
Повний текст джерела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.
Повний текст джерелаBergé, Pierre. "Algorithmes pour voyager sur un graphe contenant des blocages." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS480.
Повний текст джерелаWe study NP-hard problems on graphs with blockages seen as models of networks which are exposed to risk of failures.We treat cut problems via the parameterized complexity framework. The cutset size p is taken as a parameter. Given a set of sources {s1,...,sk} and a target $t, we propose an algorithm which builds a small edge cut of size p separating at least r sources from t. This NP-complete problem is called Partial One-Target Cut. It belongs to the family of multiterminal cut problems. Our algorithm is fixed-parameter tractable (FPT) as its execution takes $2^{O(p^2)}n^{O(1)}$. We prove that the vertex version of this problem, which imposes cuts to contain vertices instead of edges, is W[1]-hard. Then, we design an FPT algorithm which counts the minimum vertex (S,T)-cuts of an undirected graph in time $2^{O(plog p)}n^{O(1)}$.We provide numerous results on the competitive ratio of both deterministic and randomized strategies for the Canadian Traveller Problem. The optimal ratio obtained for the deterministic strategies on general graphs is 2k+1, where k is a given upper bound on the number of blockages. We show that randomized strategies which do not use memory cannot improve the bound 2k+1. In addition, we discuss the tightness of lower bounds on the competitiveness of randomized strategies. The distance competitive ratio for a group of travellers possibly equipped with telecommunication devices is studied. Eventually, a strategy dedicated to equal-weight chordal graphs is proposed while another one is built for graphs with small maximum (s,t)-cuts. Both strategies outperform the ratio 2k+1
Khosravian, Ghadikolaei Mehdi. "Extension of NP Optimization Problems." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED064.
Повний текст джерелаThe problem of determining the quality of a partial solution occurs in almost every algorithmic approach that gradually computes a global solution. Pruning search trees, proving approximation guarantees, or the efficiency of enumeration strategies usually require a suitable way to decide if a given partial solution is a reasonable candidate to pursue for extension to a global one, of assured quality. In this thesis, we study a special type of optimization problems, called extension problems for a large number of optimization problems on graphs. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimization problem can be solved in polynomial time. We present many positive/negative hardness and approximation results for different input scenarios. Moreover, the parameterized complexity of extension problems with respect to size of partial solutions, as well as the optimality of some exact algorithms under the Exponential-Time Hypothesis (ETH) are studied