Name
Abstract | ||
|---|---|---|
In various areas of computer science and mathematics, including scientific computing, task scheduling and VLSI design, the graph concept is used for modeling purposes, and graph partitioning algorithms are required to obtain solutions. For example, with increasing complexities of circuit design the circuit graphs may have several millions of nodes, while the CAD tools, like e.g. layout or visualization tools, work best on smaller subproblems. Thus, often partitions with a large number of components have to be determined. We present GREEDY IIP, a partitioning algorithm based on a sequence of greedy local operations. These operations are combined in an iterative manner directed by a restricted hill climbing approach. The algorithm is particularly successful, if a large number of final partitions, i.e. more than 1000, has to be computed. Experimental results on a large number of benchmarks are given. In comparison to the state-of-the-art tools GREEDY IIP shows significant advantages with respect to quality, space requirements and in many cases also with respect to run time |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1109/DSD.2001.952117 | DSD |
Keywords | Field | DocType |
cad tool,graph partitioning algorithms,greedy iterative improvement,vlsi design,greedy iip,large number,circuit graph,logic design,circuit graphs,circuit complexity,greedy local operations,large graphs,computer science,partitioning algorithm,restricted hill climbing approach,task scheduling,circuit design,graph concept,scheduling algorithm,scientific computing,mathematics,mathematical model,algorithm design and analysis,graph partitioning,very large scale integration,hill climbing | Logic synthesis,Hill climbing,Algorithm design,Computer science,Scheduling (computing),Parallel computing,Theoretical computer science,Greedy algorithm,Greedy randomized adaptive search procedure,Graph partition,Very-large-scale integration | Conference |
ISBN | Citations | PageRank |
0-7695-1239-9 | 1 | 0.36 |
References | Authors | |
8 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernd Becker | 1 | 855 | 73.74 |
| Thomas Eschbach | 2 | 33 | 4.00 |
| Rolf Drechsler | 3 | 531 | 34.26 |
| W. Günther | 4 | 1 | 0.36 |