tjhighley
  • Member for 5 years, 3 months
  • Last seen more than a month ago
Set of vertex-disjoint cycles maximizing different colored vertices
Accepted answer
6 votes

It cannot be solved in polynomial time, assuming P$\,\neq\,$NP. Without worrying about colors (i.e. if every vertex had the same color), it is the MAX SIZE EXCHANGE problem from the Kidney Exchange ...

View answer
Finding trading cycles
Accepted answer
5 votes

I'm assuming that items are always traded 1-for-1. How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?" If ...

View answer
how to check whether a flow network contains unique maximum flow?
4 votes

Find a maximum flow. Then create m new flow networks: one for each edge in the maximum flow. In each new configuration, reduce the capacity of one of the edges to an amount just below its flow. ...

View answer
Given 2 sets of n points: minimize sum of traveled distances
Accepted answer
4 votes

As mentioned in the problem statement, this is the Assignment Problem (minimum weight bipartite matching) where it is known that the weights are the Euclidean distances. There have been several ...

View answer
How can I find matchings in a Bipartite graph beginning with specific vertices?
2 votes

To make this a minimum-cost perfect matching problem, split each node as you indicated (sending/receiving). Add a high-cost edge from each node's sending node to its own receiving node. This high-...

View answer
Complexity of shortest paths if paths have to use edges from different partitions
2 votes

If it helps, the problem you are trying to solve is looking for a "rainbow path" between the two vertices. It's a relatively new area of research, and there's now a book: Rainbow Connections of ...

View answer
Vertex-disjoint cycles passing through a collection of vertices
2 votes

If $U$=$V$ it reduces to a matching problem by splitting all of the vertices into a left-vertex and a right-vertex to create a corresponding bipartite graph. All existing edges in the original graph ...

View answer
Optimal flow in a network with non-constant edges' weights
1 votes

Your problem is a generalization of the Longest Path problem, which is NP-hard. If the functions are constant and every conversion increases the amount of money, then there's no reason not to convert ...

View answer
Minimum cost to match $n$ people with $m$ shops
1 votes

To convert your problem into minimum cost bipartite perfect matching, pad the smaller side with dummy vertices. Make your graph a complete bipartite graph where the cost of each edge is the Manhattan ...

View answer
Inheritance problem (JAVA)
Accepted answer
1 votes

The variable $ob$ is an object reference variable of type $A$. As such, it can only reference those attributes and methods defined in $A$. The attribute $e$ is defined in $B$, not $A$, so $ob$ ...

View answer
Are two states equivalent in a DFA if on the same input the states transition to each other?
Accepted answer
1 votes

Not necessarily. If there is another symbol in the alphabet, $c$, such that $q_1$ transitions to $q_4$ on $c$ but $q_2$ transitions to $q_5$ then they are clearly not equivalent.

View answer
Are there FPTASs for the min cost flow problem?
0 votes

You may want to look at "Adding Multiple Cost Constraints to Combinatorial Optimization Problems, with Applications to Multicommodity Flows" by David Karger and Serge Plotkin (STOC 1995). They find a ...

View answer
How to prove with induction
Accepted answer
0 votes

The first step is the basis step (or base case). For this problem, that is when $b = 1$. We identify that as the base case because $P(a, b)$ is a piece-wise function, and the non-recursive case is ...

View answer
How to determine $10^{\log n}$ and $3n^2$ which grows faster asymptotically?
0 votes

As others have noted, it depends on the base of the $log$. When a base is not given, in computer science it is generally assumed to be 2. In mathematics, it is generally assumed to be $e$. In ...

View answer