Добірка наукової літератури з теми "Graphes paramétrés"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Зміст
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Graphes paramétrés".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "Graphes paramétrés"
Cueto, María Angélica, and Shaowei Lin. "Tropical secant graphs of monomial curves." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AN,..., Proceedings (January 1, 2010). http://dx.doi.org/10.46298/dmtcs.2820.
Повний текст джерелаEngström, Alexander, and Patrik Norén. "Polytopes from Subgraph Statistics." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AO,..., Proceedings (January 1, 2011). http://dx.doi.org/10.46298/dmtcs.2912.
Повний текст джерелаPilaud, Vincent. "Signed tree associahedra." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AT,..., Proceedings (January 1, 2014). http://dx.doi.org/10.46298/dmtcs.2402.
Повний текст джерелаДисертації з теми "Graphes paramétrés"
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.
Повний текст джерела