All Questions
14 questions
1
vote
1
answer
54
views
Complexity of maximum weight-sum matching for cycle graphs
I need to determine a matching with maximal weight-sum for a cycle graph with positive, negative and zero edge-weights.
Question:
What is the fastest way of calculating such a matching?
Because of ...
- 13.2k
1
vote
1
answer
97
views
Algorithmic complexity of calculating maximum weight $k$-regular subgraphs
Question:
what is known about the complexity of calculating the heaviest $k$-regular subgraph of a weighted symmetric graph if edge-weights can also be negative?
Please note that in contrast to $k$-...
- 13.2k
3
votes
1
answer
177
views
Maximum weight matching with classes of edges in a multi-edge bipartite graph
Consider a multi-edge bipartite graph $G = (L, R, E)$, with $|L| = |R| = n$, such that any $x \in L, y \in R$ have precisely two edges in $E$, $(x, y)_r, (x,y)_b$. We can imagine that we are assigning ...
- 31
1
vote
0
answers
61
views
Algorithm for minimum weight matching with "tree topology"
Given a finite graph $G(V,E)$ with undirected and weighted edges, whose set of vertices $V$ is partitioned into a collection $\mathfrak{P}=\lbrace V_1,\,\dots,\,V_k\rbrace$ of non-empty and pairwise ...
- 13.2k
4
votes
2
answers
381
views
Max weighted matching where edge weight depends on the matching
Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other ...
- 367
2
votes
1
answer
55
views
maximum weighted matching with weights being sets
Given a set $S$ and a bipartite graph $G$, each edge $v\in E(G)$ covers a subset $S_v$ of $S$. My problem is to find a matching maximizing the number of covered elements, i.e., denote $V$ the set of ...
- 367
3
votes
1
answer
151
views
Practical calculation of minimum weight vertex-disjoint cycle covers
How are minimum-weight vertex-disjoint cycle covers of large dense symmetric graphs actually calculated in actual implementations?
I know that the problem can be reduced to general matching by ...
- 13.2k
1
vote
1
answer
311
views
Tutte's Reduction of Minimum Weight d-Factors to Matching
I am currently interested in minimum weight regular d-spanners (i.e. d-factors) of complete graphs. When searching the internet for related articles, I came across this one, which is concerned with ...
- 13.2k
2
votes
1
answer
3k
views
2-approximation algorithm for Minimum Maximal Matching (MMM) problem
I'm looking to find a 2-approximation algorithm (pseudocode) for the minimum maximal matching problem. I tried to find one but I did not manage. I want to use it to implement a program in java. Can ...
- 133
2
votes
0
answers
120
views
Blossoms and Colorings
There is a striking analogy between finding maximum matchings in graphs and determining the chromatic number of graphs: both problems are fairly easy for bipartite graphs, but harder, resp. too hard ...
- 13.2k
5
votes
0
answers
244
views
When does a "stable" assignment of buyers into goods exist?
Consider a setting of $n$ buyers and $m$ goods.
We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...
- 618
5
votes
2
answers
4k
views
Solving assignment problem using Hungarian method vs min cost max flow problem
The traditional solution for the assignment problem is the Hungarian method - it's complexity is O(V^4) or O(V^3) if using Edmonds method.
However, it can also be reduced to a min cost max flow ...
- 201
4
votes
1
answer
1k
views
Polygamous stable marriage/ assignment problem
I'm not sure under which 'algorithm' it falls under, but here is the problem:
I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...
- 201
6
votes
1
answer
2k
views
Maximum bipartite graph (1,n) "matching"
Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out ...
- 161