Search Results

It is known, that Minimum Weight Perfect Matching can be calculated in $O(n^3)$; Furthermore, it is possible, that the edge sets of the Minimum Weight Perfect Matching and of the Maximum Weight Perfe …

This is a follow-up question to Minimum-weight disjoint union of perfect matchings: let $G$ be a complete symmetric graph with $2n$ vertices, whose edges are mapped to their weights by $\omega()$ and …

It is well known, that there are two basic kinds of manifolds, orientable and non-orientable ones; the most simple examples being obtained by identifying a pair of opposite sides of a rectangular stri …

Is there a counter example or proof for the claim that the lightest edge-disjoint union of a pair of perfect matchings contains the edges of the lightest perfect matching in a finite complete graph wi …

Given a complete weighted graph $G(V,E),\ |V|=2n$, calculating a minimum weight matching with $n-k$ edges can be reduced to calculating a perfect matching in $H(V+U,E+F),\ |U|=2k,\ F=(u\in U,v\in V),\ …

Question: what is known about minimum/maximum weight perfect matchings in magic squares with or without special properties like e.g. being pandiagonal? I am especially interested minimal/maximal cel …

There is a fairly rich classification on graphs with respect to the existence of Hamiltonian cycles either in unmodified graphs or after certain small modifications. Do there also exist such classi …

If $G\left(A\cup B,\ E=\lbrace\lbrace a, b\rbrace\,|\, a\in A,\, b\in B\rbrace\right)$ is a weighted bipartite graph and $M_0$ an initial perfect matching, then the optimality of $M_0$ can be verified …

let $\Delta$ be the triangle whose corners $A$, $B$, $C$ points in general position in Euclidean plane and, let $D$ be a fourth point inside $\Delta$. Question: what is known about the cons …

Is there a sound proof of or a counter example to the following conjecture: if $\boldsymbol{A}^T=\boldsymbol{A}$ is the cost-matrix of a bipartite assignment problem with unique optimal assignment, t …

The subject of this question are perfect matchings of a complete undirected graph $G(V,E), n:=\mathrm{card}(V)=2k$, without self-loops or parallel edges and $n=2k$ vertices. The objective is to determ …

Question: What can be recommended for finding optimal perfect matchings in large bipartite graphs with small vertex degree if the edge-weights are positive real values? I am looking for algor …

pyMCFSimplex seems to best fit my needs. "It is a free Python port of a Python Wrapper for MCFSimplex. pyMCFimplex is a Python-Wrapper for the C++ MCFSimplex Solver Class from the Operations Research …

I have by accident found an interesting kind of spanner of complete symmetric graphs $G(V,E)$ with weighted edges. What I actually had planned was to implement an algorithm for calculating certain non …

Question: are there any algorithms, resp. what can be recommended, for calculating perfect matchings with the property that the variance of their edge's weights is minimal?