Literatura científica selecionada sobre o tema "Polytope des couplages parfaits"
Crie uma referência precisa em APA, MLA, Chicago, Harvard, e outros estilos
Consulte a lista de atuais artigos, livros, teses, anais de congressos e outras fontes científicas relevantes para o tema "Polytope des couplages parfaits".
Ao lado de cada fonte na lista de referências, há um botão "Adicionar à bibliografia". Clique e geraremos automaticamente a citação bibliográfica do trabalho escolhido no estilo de citação de que você precisa: APA, MLA, Harvard, Chicago, Vancouver, etc.
Você também pode baixar o texto completo da publicação científica em formato .pdf e ler o resumo do trabalho online se estiver presente nos metadados.
Artigos de revistas sobre o assunto "Polytope des couplages parfaits"
Kim, Jang Soo. "Proofs of two conjectures of Kenyon and Wilson on Dyck tilings". Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AR,..., Proceedings (1 de janeiro de 2012). http://dx.doi.org/10.46298/dmtcs.3046.
Texto completo da fonteMusiker, Gregg, e Ralf Schiffler. "Cluster algebras of unpunctured surfaces and snake graphs". Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AK,..., Proceedings (1 de janeiro de 2009). http://dx.doi.org/10.46298/dmtcs.2685.
Texto completo da fonteRubey, Martin, e Bruce W. Westbury. "Combinatorics of symplectic invariant tensors". Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings, 27th..., Proceedings (1 de janeiro de 2015). http://dx.doi.org/10.46298/dmtcs.2508.
Texto completo da fonteHeitsch, Christine E., e Prasad Tetali. "Meander Graphs". Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AO,..., Proceedings (1 de janeiro de 2011). http://dx.doi.org/10.46298/dmtcs.2926.
Texto completo da fonteTeses / dissertações sobre o assunto "Polytope des couplages parfaits"
Pisanu, Francesco. "On box-total dual integrality and total equimodularity". Electronic Thesis or Diss., Paris 13, 2023. http://www.theses.fr/2023PA131044.
Texto completo da fonteIn this thesis, we study box-totally dual integral (box-TDI) polyhedra associated with severalproblems and totally equimodular matrices. Moreover, we study the complexity of some funda-mental questions related to them.We start by considering totally equimodular matrices, which are matrices such that, forevery subset of linearly independent rows, all nonsingular maximal submatrices have the samedeterminant in absolute value. Despite their similarities with totally unimodular matrices, wehighlight several differences, even in the case of incidence and adjacency matrices of graphs.As is well-known, the incidence matrix of a given graph is totally unimodular if and only if thegraph is bipartite. However, the total equimodularity of an incidence matrix depends on whetherwe consider the vertex-edge or the edge-vertex representation. We provide characterizations forboth cases. As a consequence, we prove that recognizing whether a given polyhedron is box-TDIis a co-NP-complete problem.Characterizing the total unimodularity or total equimodularity of the adjacency matrix of agiven bipartite graph remains unsolved, while we solved the corresponding problem in the case oftotal equimodularity when the graph is nonbipartite.In a later part of this work, we characterize the graphs for which the perfect matching polytope(PMP) is described by trivial inequalities and the inequalities corresponding to tight cuts. Tightcuts are defined as cuts that share precisely one edge with each perfect matching. We thenprove that any graph for which the corresponding PMP is box-TDI belongs to this class. Asa consequence, it turns out that recognizing whether the PMP is box-TDI is a polynomial-timeproblem. However, we provide several counterexamples showing that this class of graphs does notguarantee the box-TDIness of the PMP.Lastly, we present necessary conditions for the box-TDIness of the edge cover polytope andcharacterize the box-TDIness of the extendable matching polytope, which is the convex hull ofthe matchings included in a perfect matching
Benchetrit, Yohann. "Propriétés géométriques du nombre chromatique : polyèdres, structures et algorithmes". Thesis, Université Grenoble Alpes (ComUE), 2015. http://www.theses.fr/2015GREAM049/document.
Texto completo da fonteComputing the chromatic number and finding an optimal coloring of a perfect graph can be done efficiently, whereas it is an NP-hard problem in general. Furthermore, testing perfection can be carried- out in polynomial-time. Perfect graphs are characterized by a minimal structure of their sta- ble set polytope: the non-trivial facets are defined by clique-inequalities only. Conversely, does a similar facet-structure for the stable set polytope imply nice combinatorial and algorithmic properties of the graph ? A graph is h-perfect if its stable set polytope is completely de- scribed by non-negativity, clique and odd-circuit inequalities. Statements analogous to the results on perfection are far from being understood for h-perfection, and negative results are missing. For ex- ample, testing h-perfection and determining the chromatic number of an h-perfect graph are unsolved. Besides, no upper bound is known on the gap between the chromatic and clique numbers of an h-perfect graph. Our first main result states that the operations of t-minors keep h- perfection (this is a non-trivial extension of a result of Gerards and Shepherd on t-perfect graphs). We show that it also keeps the Integer Decomposition Property of the stable set polytope, and use this to answer a question of Shepherd on 3-colorable h-perfect graphs in the negative. The study of minimally h-imperfect graphs with respect to t-minors may yield a combinatorial co-NP characterization of h-perfection. We review the currently known examples of such graphs, study their stable set polytope and state several conjectures on their structure. On the other hand, we show that the (weighted) chromatic number of certain h-perfect graphs can be obtained efficiently by rounding-up its fractional relaxation. This is related to conjectures of Goldberg and Seymour on edge-colorings. Finally, we introduce a new parameter on the complexity of the matching polytope and use it to give an efficient and elementary al- gorithm for testing h-perfection in line-graphs