3 ms·
Any n-dimensional grid (sometimes called a "Manhattan space") is a bipartite graph. You may find it useful that no odd-length cycles can exist in such a graph.
by Locke1689 14y ago
Any n-dimensional grid (sometimes called a "Manhattan space") is a bipartite graph. You may find it useful that no odd-length cycles can exist in such a graph.
- rhizome 14y agoWhat is a practical scenario for odd-length cycles in a grid?
- Locke1689 14y agoAh, sorry, the odd-length cycle was supposed to be a hint for Colin's problem, not an actual use of bipartite graphs. I find all the uses of bipartite graphs to be in maximal matching or similar situations.
- rhizome 14y agoStill..."scenario."
- Locke1689 14y agoThere are many reasons why you would want a maximal matching. In my case I was working on a distributed system prototype that needed to match block requests my users to cache servers. This is a maximal matching from cache servers who have these blocks available to users requesting blocks.