tjhighley
• Member for 5 years, 3 months
• Last seen more than a month ago

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 ...

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 ...

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. ...

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 ...

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-...

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 ...

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 ...

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 ...

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 ...

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$ ...

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.

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 ...

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 ...
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 ...