Relevant bibliographies by topics / Perfect matching polytope / Journal articles

Journal articles on the topic 'Perfect matching polytope'

To see the other types of publications on this topic, follow the link: Perfect matching polytope.
Author: Grafiati
Published: 7 July 2024
Last updated: 7 July 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 16 journal articles for your research on the topic 'Perfect matching polytope.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
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.
2

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Lin, Yixun, and 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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
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.
11

Huang, Chien-Chung, and Telikepalli Kavitha. "Popularity, Mixed Matchings, and Self-Duality." Mathematics of Operations Research, February 18, 2021. http://dx.doi.org/10.1287/moor.2020.1063.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
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.
12

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
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.
13

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
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.
14

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
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, and Fernando Gervilla. "Micron-to-nanoscale investigation of Cu-Fe-Ni sulfide inclusions within laurite (Ru, Os)S2 from chromitites." Mineralium Deposita, June 26, 2024. http://dx.doi.org/10.1007/s00126-024-01285-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
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.
16

Ceballos, Cesar, and Vincent Pilaud. "Cluster Algebras of Type D: Pseudotriangulations Approach." Electronic Journal of Combinatorics 22, no. 4 (December 23, 2015). http://dx.doi.org/10.37236/5282.

Full text
APA, Harvard, Vancouver, ISO, and other styles
Abstract:
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.

To the bibliography