Tag Info

Hot answers tagged graphs

2

Yes, D*-lite is a directed graph algorithm, so it works fine with asymmetric edge weights by definition. However, note that the heuristic being admissible is not sufficient. According to the paper, it must be consistent. Based on what you described, I would guess Euclidean distance would be consistent for your graph, but we can't know for sure without ...

1

I believe this is known as the "bottleneck matching" problem. Here is an algorithm for that problem. There is a straightforward algorithm. Pick a threshold $t$. Delete all edges with weight below $t$ and check whether there is a matching in that graph. Now do binary search on $t$, to find the largest $t$ such that the resulting graph has a ...

Only top voted, non community-wiki answers of a minimum length are eligible