Graph partitioning system

Details Graph partitioning system Graph partitioning system

1994-11-03

1998-05-05

Hafiz, Tariq R.

395 12, 395 20, G06F 1518

Patent

active

057488444

ABSTRACT:
A system is disclosed for computing an initial partition of a graph comprising nodes and the edges that connect the nodes. In one embodiment this initial partition is presented for subsequent use by the Kernighan-Lin system of graph partitioning. The Subject System uses a combination of a seed-growth heuristic and a stochastic-search process to compute an initial partition. The seed-growth heuristic builds a partition by iteratively augmenting an initial set of seed nodes. The search process searches for good sets of seed nodes to use. The resulting combination of seed-growth heuristic, stochastic-search process, and the Kernighan-Lin algorithm constitutes a superior system for partitioning graphs. The Subject System can be applied to graph-partitioning problems that arise in circuit design, computer architecture, routing in computer networks, database design, distributed and parallel processing, and many other domains.

REFERENCES:
Saab, Youssef and Rao, Vasant, "Fast Effective Heuristics for the Graph Bctioning Problem", IEEE Transactions On Computer-Aided Design, vol. 9, No. 1, pp. 91-98, Jan. 1990.
Shahookar, K. and Mazumder, P., "VLSI Cell Placement Techniques", ACM Computing Surveys, vol. 23, No. 2, pp. 143-220, Jun. 1991.

Affiliated with

Also associated with

Rating

Graph partitioning system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Graph partitioning system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph partitioning system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-64811