Method for automatic partitioning of node-weighted, edge-constrained graphs
US6437804B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Oct 23, 1997 |
| Grant date | Aug 20, 2002 |
| Priority date | — |
| Expiry date | Oct 23, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2111/12
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
According to an embodiment of the present invention, a method is provided for partitioning a network, comprising modeling the network as a graph comprising nodes which represent network devices, and edges which represent links between the devices, and automatically partitioning the graph into domains. One embodiment of the method includes identifying a number of anchor nodes in the graph and partitioning the domains around the anchor nodes such that each domain contains only one anchor node. Another embodiment of the method includes partitioning a graph without anchor nodes into a number of domains, and assigning controllers to each of the domains. Preferably, the method further includes assigning a weight to each node in the graph, and balancing the partitions as a function of the weight of each node in a respective partition.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.