Bibliographies thématiques / Perfect matching polytope / Articles de revues

Articles de revues sur le sujet « Perfect matching polytope »

Pour voir les autres types de publications sur ce sujet consultez le lien suivant : Perfect matching polytope.
Auteur : Grafiati
Publié le 7 juillet 2024
Mis à jour le 7 juillet 2024

Créez une référence correcte selon les styles APA, MLA, Chicago, Harvard et plusieurs autres

Choisissez une source :

Consultez les 16 meilleurs articles de revues pour votre recherche sur le sujet « Perfect matching polytope ».

À côté de chaque source dans la liste de références il y a un bouton « Ajouter à la bibliographie ». Cliquez sur ce bouton, et nous générerons automatiquement la référence bibliographique pour la source choisie selon votre style de citation préféré : APA, MLA, Harvard, Vancouver, Chicago, etc.

Vous pouvez aussi télécharger le texte intégral de la publication scolaire au format pdf et consulter son résumé en ligne lorsque ces informations sont inclues dans les métadonnées.

Parcourez les articles de revues sur diverses disciplines et organisez correctement votre bibliographie.

1

WANG, XIUMEI, WEIPING SHANG, YIXUN LIN et MARCELO H. CARVALHO. « A CHARACTERIZATION OF PM-COMPACT CLAW-FREE CUBIC GRAPHS ». Discrete Mathematics, Algorithms and Applications 06, no 02 (19 mars 2014) : 1450025. http://dx.doi.org/10.1142/s1793830914500256.

Texte intégral
Résumé :
The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings in G. This paper characterizes claw-free cubic graphs whose 1-skeleton graphs of perfect matching polytopes have diameter 1.
Styles APA, Harvard, Vancouver, ISO, etc.
2

de Carvalho, Marcelo H., Cláudio L. Lucchesi et U. S. R. Murty. « The perfect matching polytope and solid bricks ». Journal of Combinatorial Theory, Series B 92, no 2 (novembre 2004) : 319–24. http://dx.doi.org/10.1016/j.jctb.2004.08.003.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
3

Lin, Ruizhi, et Heping Zhang. « Fractional matching preclusion number of graphs and the perfect matching polytope ». Journal of Combinatorial Optimization 39, no 3 (29 janvier 2020) : 915–32. http://dx.doi.org/10.1007/s10878-020-00530-2.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
4

Rispoli, Fred J. « The Monotonic Diameter of the Perfect 2-matching Polytope ». SIAM Journal on Optimization 4, no 3 (août 1994) : 455–60. http://dx.doi.org/10.1137/0804025.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
5

Bian, Hong, et Fuji Zhang. « The graph of perfect matching polytope and an extreme problem ». Discrete Mathematics 309, no 16 (août 2009) : 5017–23. http://dx.doi.org/10.1016/j.disc.2009.03.009.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
6

Lin, Yixun, et Xiumei Wang. « Core index of perfect matching polytope for a 2-connected cubic graph ». Discussiones Mathematicae Graph Theory 38, no 1 (2018) : 189. http://dx.doi.org/10.7151/dmgt.2001.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
7

Behrend, Roger E. « Fractional perfect b -matching polytopes I : General theory ». Linear Algebra and its Applications 439, no 12 (décembre 2013) : 3822–58. http://dx.doi.org/10.1016/j.laa.2013.10.001.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
8

Wang, Xiumei, et Yixun Lin. « Three-matching intersection conjecture for perfect matching polytopes of small dimensions ». Theoretical Computer Science 482 (avril 2013) : 111–14. http://dx.doi.org/10.1016/j.tcs.2013.02.023.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
9

Rispoli, Fred J. « The monotonic diameter of the perfect matching and shortest path polytopes ». Operations Research Letters 12, no 1 (juillet 1992) : 23–27. http://dx.doi.org/10.1016/0167-6377(92)90018-x.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
10

Atserias, Albert, Anuj Dawar et Joanna Ochremiak. « On the Power of Symmetric Linear Programs ». Journal of the ACM 68, no 4 (28 juillet 2021) : 1–35. http://dx.doi.org/10.1145/3456297.

Texte intégral
Résumé :
We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs, while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991), showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem.
Styles APA, Harvard, Vancouver, ISO, etc.
11

Huang, Chien-Chung, et Telikepalli Kavitha. « Popularity, Mixed Matchings, and Self-Duality ». Mathematics of Operations Research, 18 février 2021. http://dx.doi.org/10.1287/moor.2020.1063.

Texte intégral
Résumé :
Our input instance is a bipartite graph G where each vertex has a preference list ranking its neighbors in a strict order of preference. A matching M is popular if there is no matching N such that the number of vertices that prefer N to M outnumber those that prefer M to N. Each edge is associated with a utility and we consider the problem of matching vertices in a popular and utility-optimal manner. It is known that it is NP-hard to compute a max-utility popular matching. So we consider mixed matchings: a mixed matching is a probability distribution or a lottery over matchings. Our main result is that the popular fractional matching polytope PG is half-integral and in the special case where a stable matching in G is a perfect matching, this polytope is integral. This implies that there is always a max-utility popular mixed matching which is the average of two integral matchings. So in order to implement a max-utility popular mixed matching in G, we need just a single random bit. We analyze the popular fractional matching polytope whose description may have exponentially many constraints via an extended formulation with a linear number of constraints. The linear program that gives rise to this formulation has an unusual property: self-duality. The self-duality of this LP plays a crucial role in our proof. Our result implies that a max-utility popular half-integral matching in G and also in the roommates problem (where the input graph need not be bipartite) can be computed in polynomial time.
Styles APA, Harvard, Vancouver, ISO, etc.
12

Mori, Kenta. « Toric Rings of Perfectly Matchable Subgraph Polytopes ». Graphs and Combinatorics 39, no 6 (4 novembre 2023). http://dx.doi.org/10.1007/s00373-023-02719-8.

Texte intégral
Résumé :
AbstractThe perfectly matchable subgraph polytope of a graph is a (0,1)-polytope associated with the vertex sets of matchings in the graph. In this paper, we study algebraic properties (compressedness, Gorensteinness) of the toric rings of perfectly matchable subgraph polytopes. In particular, we give a complete characterization of a graph whose perfectly matchable subgraph polytope is compressed.
Styles APA, Harvard, Vancouver, ISO, etc.
13

Tagami, Makoto. « Gorenstein Polytopes Obtained from Bipartite Graphs ». Electronic Journal of Combinatorics 17, no 1 (5 janvier 2010). http://dx.doi.org/10.37236/280.

Texte intégral
Résumé :
Beck et al. characterized the grid graphs whose perfect matching polytopes are Gorenstein and they also showed that for some parameters, perfect matching polytopes of torus graphs are Gorenstein. In this paper, we complement their result, that is, we characterize the torus graphs whose perfect matching polytopes are Gorenstein. Beck et al. also gave a method to construct an infinite family of Gorenstein polytopes. In this paper, we introduce a new class of polytopes obtained from graphs and we extend their method to construct many more Gorenstein polytopes.
Styles APA, Harvard, Vancouver, ISO, etc.
14

Cardinal, Jean, et Raphael Steiner. « Inapproximability of shortest paths on perfect matching polytopes ». Mathematical Programming, 21 octobre 2023. http://dx.doi.org/10.1007/s10107-023-02025-4.

Texte intégral
Styles APA, Harvard, Vancouver, ISO, etc.
15

González-Jiménez, José María, Igor González-Pérez, Gaëlle Plissart, Amira R. Ferreira, Erwin Schettino, Lola Yesares, Manuel E. Schilling, Alexandre Corgne et Fernando Gervilla. « Micron-to-nanoscale investigation of Cu-Fe-Ni sulfide inclusions within laurite (Ru, Os)S2 from chromitites ». Mineralium Deposita, 26 juin 2024. http://dx.doi.org/10.1007/s00126-024-01285-0.

Texte intégral
Résumé :
AbstractThis paper provides a top-down nanoscale analysis of Cu-Ni-Fe sulfide inclusions in laurite from the Taitao ophiolite (Chile) and the Kevitsa mafic-ultramafic igneous intrusion (Finland). High-resolution transmission electron microscopy (HRTEM) reveal that Cu-Ni-Fe sulfide inclusions are euhedral to (sub)-anhedral (i.e., droplet-like) and form single, biphasic or polyphasic grains, made up of different polymorphs, polytypes and polysomes even within a single sulfide crystal. Tetragonal (I4$$\stackrel{-}{2}$$d) and cubic (F$$\stackrel{-}{4}$$3m) chalcopyrite (CuFeS2) host frequent fringes of bornite (Cu5FeS4; cubic F$$\stackrel{-}{4}$$3m and/or orthorhombic Pbca) ± talnakhite (Cu9(Fe, Ni)8S16; cubic I$$\stackrel{-}{4}$$3m) ± pyrrhotite (Fe1 − xS; monoclinic C2/c polytype 4C and orthorhombic Cmca polytype 11C) ± pentlandite ((Ni, Fe)9S8; cubic Fm3m). Pentlandite hosts fringes of pyrrhotite, bornite and/or talnakhite. Laurite and Cu-Fe-Ni sulfide inclusions display coherent, semi-coherent and incoherent crystallographic orientation relationships (COR), defined by perfect edge-to-edge matching, as well as slight (2–4º) to significant (45º) lattice misfit. These COR suggest diverse mechanisms of crystal growth of Cu-Fe-Ni sulfide melt mechanically trapped by growing laurite. Meanwhile, the mutual COR within the sulfide inclusions discloses: (1) Fe-Ni-S melt solidified into MSS re-equilibrated after cooling into pyrrhotite ± pentlandite, (2) Cu-Ni-Fe-S melts crystallized into the quaternary solid solution spanning the compositional range between heazlewoodite [(Ni, Fe)3±xS2] (Hzss) and ISS [(Cu1±x, Fe1±y)S2]. Additionally, nanocrystallites (50–100 nm) of Pt-S and iridarsenite (IrAsS) accompanying the sulfide inclusions spotlight the segregation of PGE-rich sulfide and arsenide melt earlier and/or contemporarily to laurite crystallization from the silicate magmas. Cobaltite (CoAsS)-gersdorffite (NiAsS) epitaxially overgrown on laurite further supports the segregation of arsenide melts at early stages of chromitite formation.
Styles APA, Harvard, Vancouver, ISO, etc.
16

Ceballos, Cesar, et Vincent Pilaud. « Cluster Algebras of Type D : Pseudotriangulations Approach ». Electronic Journal of Combinatorics 22, no 4 (23 décembre 2015). http://dx.doi.org/10.37236/5282.

Texte intégral
Résumé :
We present a combinatorial model for cluster algebras of type $D_n$ in terms of centrally symmetric pseudotriangulations of a regular $2n$ gon with a small disk in the centre. This model provides convenient and uniform interpretations for clusters, cluster variables and their exchange relations, as well as for quivers and their mutations. We also present a new combinatorial interpretation of cluster variables in terms of perfect matchings of a graph after deleting two of its vertices. This interpretation differs from known interpretations in the literature. Its main feature, in contrast with other interpretations, is that for a fixed initial cluster seed, one or two graphs serve for the computation of all cluster variables. Finally, we discuss applications of our model to polytopal realizations of type $D$ associahedra and connections to subword complexes and $c$-cluster complexes.
Styles APA, Harvard, Vancouver, ISO, etc.
Nous offrons des réductions sur tous les plans premium pour les auteurs dont les œuvres sont incluses dans des sélections littéraires thématiques. Contactez-nous pour obtenir un code promo unique!

Vers la bibliographie