Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Fast Algorithm
Minimum Cut
System Design
Related Publications
(1)
A Simple Hypergraph Min Cut Algorithm
Subscribe
Academic
Publications
A fast hypergraph mincut algorithm for circuit partitioning
A fast hypergraph mincut algorithm for circuit partitioning,10.1016/S01679260(00)000080,Integration,Waikei Mak,D. F. Wong
Edit
A fast hypergraph mincut algorithm for circuit partitioning
(
Citations: 9
)
BibTex

RIS

RefWorks
Download
Waikei Mak
,
D. F. Wong
Circuit partitioning is one of the central problems in VLSI system design. The primary objective of circuit partitioning is to minimize the number of interconnections between different components of the partitioned circuit. So the circuit partitioning problem is closely related to the
minimum cut
problem. Recently, two very fast algorithms for computing minimum cuts in graphs were reported (Nagamochi and Ibaraki; SIAM J. Discrete Math. 5(1) (1992) 54; Stoer and Wagner, J. ACM 44(4) (1997) 585). However, it is known that a circuit netlist cannot be accurately modeled by a graph, but only by a hypergraph. In this paper, we present the fastest algorithm known today for computing a
minimum cut
in a hypergraph which is a nontrivial extension of the result in Stoer and Wagner (J. ACM 44(4) (1997) 586). Since the netlist of a circuit can be modeled naturally as a hypergraph, this opens the opportunity for finding veryhighquality solutions for the circuit partitioning problem. Unlike most
minimum cut
algorithms which rely on flow computations in a network, ours is a nonflowbased algorithm.
Journal:
Integration
, vol. 30, no. 1, pp. 111, 2000
DOI:
10.1016/S01679260(00)000080
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.sciencedirect.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
(
linkinghub.elsevier.com
)
More »
Citation Context
(6)
...Klimmek and Wagner [9] and Mak and Wong [
13
] extended an algorithm proposed by Stoer and Wagner [16] for the minimum cut problem in graphs to hypergraphs...
Takuro Fukunaga
.
Computing Minimum Multiway Cuts in Hypergraphs from Hypertree Packings
...Traditional mincut based circuit partitioning method [
2
] is not good and not enough for analog circuit synthesis task because the target partitioning is not only for netlist, but also for the performance...
...Traditional circuit partitioning is mincut based in major [
2
], which only gets mincut as optimization target for partitioning with ignorance of the circuit functionality, even the basic unit circuit and local feedbacks can be divided into two parts...
Yuping Wu
,
et al.
Parallel on Analog Circuit Synthesis
...Klimmek and Wagner [13] and Mak and Wong [
16
] extended Stoer and Wagner’s algorithm [21] to hypergraphs and gave an O(dn + n 2 log n) algorithm for the minimum cut problem in hypergraphs, where d is the sum of the degrees of all the vertices...
Mingyu Xiao
.
Finding Minimum 3Way Cuts in Hypergraphs
...16 The tractability of the hypergraph minstcut problem is also established in [
13
]...
T. K. Satish Kumar
.
A Framework for Hybrid Tractability Results in Boolean Weighted Constr...
...Its generalization to hypergraphs [11,
12
] has a runtime of O(np + n 2 logn)...
Marko Samer
,
et al.
Complexity and Applications of EdgeInduced VertexCuts
References
(10)
Modeling Hypergraphs by Graphs with the Same Mincut Properties
(
Citations: 36
)
Edmund Ihler
,
Dorothea Wagner
,
Frank Wagner
Journal:
Information Processing Letters  IPL
, vol. 45, no. 4, pp. 171175, 1993
A simple mincut algorithm
(
Citations: 150
)
Mechthild Stoer
,
Frank Wagner
Journal:
Journal of The ACM  JACM
, vol. 44, no. 4, pp. 585591, 1997
A new approach to the minimum cut problem
(
Citations: 159
)
David R. Karger
,
Clifford Stein
Journal:
Journal of The ACM  JACM
, vol. 43, no. 4, pp. 601640, 1996
Physical design automation of vlsi systems
(
Citations: 149
)
B. T. Preas
,
M. J. Lorenzetti
Published in 1988.
Recent directions in netlist partitioning: a survey
(
Citations: 253
)
Charles J Alpert
,
Andrew B Kahng
Journal:
Integration
, vol. 19, no. 1, pp. 181, 1995
Sort by:
Citations
(9)
Computing Minimum Multiway Cuts in Hypergraphs from Hypertree Packings
(
Citations: 3
)
Takuro Fukunaga
Conference:
Integer Programming and Combinatorial Optimization  IPCO
, pp. 1528, 2010
Parallel on Analog Circuit Synthesis
Yuping Wu
,
Lan Chen
,
Tianchun Ye
Conference:
International Conference on Computational Intelligence and Software Engineering  CiSE
, 2009
Finding Minimum 3Way Cuts in Hypergraphs
(
Citations: 5
)
Mingyu Xiao
Conference:
Theory and Applications of Models of Computation  TAMC
, pp. 270281, 2008
A Framework for Hybrid Tractability Results in Boolean Weighted Constraint Satisfaction Problems
(
Citations: 3
)
T. K. Satish Kumar
Conference:
Principles and Practice of Constraint Programming  CP
, pp. 282297, 2008
Mathematical methods for physical layout of printed circuit boards: an overview
Nadine Abboud
,
Martin Grötschel
,
Thorsten Koch
Journal:
Or Spektrum
, vol. 30, no. 3, pp. 453468, 2008