Graph partitioning with natural cuts
US8738559B2 · kind B2 · utility
6Cited by
5References
15Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Jan 24, 2011 |
| Grant date | May 27, 2014 |
| Priority date | — |
| Expiry date | Oct 23, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG01C21/387
- WIPO fieldMeasurement
- WIPO sectorInstruments
Abstract
Graph partitioning techniques are based on the notion of natural cuts. A filtering phase performs a series of minimum cut computations to identify and contract dense regions of the graph. This reduces the graph size significantly, but preserves its general structure. An assembly phase uses a combination of greedy and local search heuristics to assemble the final partition. The techniques may be used on road networks, which have an abundance of natural cuts (such as bridges, mountain passes, and ferries).
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.