On the other hand, if arcs represent roads between towns and two towns merge, it makes sense to keep the arcs separate: if there's a road from each of $A$ and $B$ to $C$ and $A$ and $B$ merge, there are still two roads from the merged town to $C$. Orlin is keeping them separate.įor example, if the arcs represent trading relationships between companies, it makes sense to merge the arcs: if companies $A$ and $B$ both sell to $C$ and $A$ and $B$ merge, it makes more sense to say that $C$ is a customer of the new company once, with a single arc, than to say that it's a customer twice, by having two arcs. In some contexts, you might want to replace multiple arcs between the same two nodes with a single arc whose weight (or capacity or whatever it's being called) is the sum of the weights of the original arcs in other contexts, it might make more sense to keep them separate.
We point out that the contraction operation may lead to the creation of multiple arcs, i.e., several arcs with the same head and tale nodes. The very next sentence (!) of Orlin's paper says # Note that we also have an edge from 6 to 6, i.e. Should the application of the contraction operation yield the following directed graph, where the newly introduced node $p$ has the id $6$? 0 -> 6, 5Ħ -> 3, 3, 5, 6 # Note that we got two edges from node 6 to node 3. node 0 has an edge to the nodes 1, 2 and 5 node 5 has no outgoing edges node 3 has an edge to node 4 and so on. $b$ and $p$ are functions defining values for certain properties of a node their meaning is unimportant for understanding contraction.Ĭonsider the following graph described in "adjacency speak", where e.g.
The contraction operation consists of: letting $b(p) = b(k) + b(\ell)$ and $e(p) = e(k) + e(\ell)$ replacing eachĮdge $(i, k)$ or $(i, \ell)$ by the edge $(i, p)$ replacing each edge $(k, i)$ or $(\ell, i)$ by the edge $(p, i)$ and letting the cost of an edge in the contracted network equal that of the edge it replaces. any edge, say $(k, \ell)$, can be contracted into a single node $p$. ORLIN - A FASTER STRONGLY POLYNOMIAL MINIMUM COST Let me cite the definition I do have at hand: Assuming an adjacency list as data structure of a directed Graph, it is not completely clear to me how "contraction of an edge" is defined.
0 kommentar(er)
