A fast hypergraph minimum cut algorithm

W. K. Mak; D. F. Wong

doi:10.1109/ISCAS.1999.780122

A fast hypergraph minimum cut algorithm

Research output: Contribution to journal › Conference article › peer-review

Abstract

We present the fastest algorithm known today for computing a global minimum cut in a hypergraph. Unlike most minimum cut algorithms which rely on flow computations in a network, ours is a non-flow based algorithm. Since the netlist of a circuit can be modelled naturally as a hypergraph, this opens the opportunity for finding very high quality solutions for the circuit partitioning problem.

Original language	English (US)
Pages (from-to)	VI-170-VI-173
Journal	Proceedings - IEEE International Symposium on Circuits and Systems
Volume	6
DOIs	https://doi.org/10.1109/ISCAS.1999.780122
State	Published - 1999
Externally published	Yes
Event	Proceedings of the 1999 IEEE International Symposium on Circuits and Systems, ISCAS '99 - Orlando, FL, USA Duration: May 30 1999 → Jun 2 1999

ASJC Scopus subject areas

Electrical and Electronic Engineering

Online availability

10.1109/ISCAS.1999.780122

Library availability

Discover UIUC Full Text

Cite this

@article{8d387a5c870d406db920c530bb104f45,

title = "A fast hypergraph minimum cut algorithm",

abstract = "We present the fastest algorithm known today for computing a global minimum cut in a hypergraph. Unlike most minimum cut algorithms which rely on flow computations in a network, ours is a non-flow based algorithm. Since the netlist of a circuit can be modelled naturally as a hypergraph, this opens the opportunity for finding very high quality solutions for the circuit partitioning problem.",

author = "Mak, {W. K.} and Wong, {D. F.}",

year = "1999",

doi = "10.1109/ISCAS.1999.780122",

language = "English (US)",

volume = "6",

pages = "VI--170--VI--173",

journal = "Proceedings - IEEE International Symposium on Circuits and Systems",

issn = "0271-4310",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "Proceedings of the 1999 IEEE International Symposium on Circuits and Systems, ISCAS '99 ; Conference date: 30-05-1999 Through 02-06-1999",

}

TY - JOUR

T1 - A fast hypergraph minimum cut algorithm

AU - Mak, W. K.

AU - Wong, D. F.

PY - 1999

Y1 - 1999

N2 - We present the fastest algorithm known today for computing a global minimum cut in a hypergraph. Unlike most minimum cut algorithms which rely on flow computations in a network, ours is a non-flow based algorithm. Since the netlist of a circuit can be modelled naturally as a hypergraph, this opens the opportunity for finding very high quality solutions for the circuit partitioning problem.

AB - We present the fastest algorithm known today for computing a global minimum cut in a hypergraph. Unlike most minimum cut algorithms which rely on flow computations in a network, ours is a non-flow based algorithm. Since the netlist of a circuit can be modelled naturally as a hypergraph, this opens the opportunity for finding very high quality solutions for the circuit partitioning problem.

UR - http://www.scopus.com/inward/record.url?scp=0032678368&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032678368&partnerID=8YFLogxK

U2 - 10.1109/ISCAS.1999.780122

DO - 10.1109/ISCAS.1999.780122

M3 - Conference article

AN - SCOPUS:0032678368

SN - 0271-4310

VL - 6

SP - VI-170-VI-173

JO - Proceedings - IEEE International Symposium on Circuits and Systems

JF - Proceedings - IEEE International Symposium on Circuits and Systems

T2 - Proceedings of the 1999 IEEE International Symposium on Circuits and Systems, ISCAS '99

Y2 - 30 May 1999 through 2 June 1999

ER -

A fast hypergraph minimum cut algorithm

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this