A fast hypergraph minimum cut algorithm

Wai-Kei Mak; D. F. Wong

doi:10.1109/ISCAS.1999.780122

A fast hypergraph minimum cut algorithm

Wai-Kei Mak
, D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › 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
Title of host publication	Proceedings of 1999 IEEE International Symposium on Circuits and Systems, ISCAS 1999
Publisher	IEEE
Pages	VI-170-VI-173
Number of pages	4
Volume	6
ISBN (Print)	0780354710
DOIs	https://doi.org/10.1109/ISCAS.1999.780122
Publication status	Published - 30 May 1999
Event	1999 IEEE International Symposium on Circuits and Systems, ISCAS 1999 - Orlando, United States Duration: 30 May 1999 → 2 Jun 1999 https://ieeexplore.ieee.org/xpl/conhome/6311/proceeding (Conference proceedings)

Publication series

Name	Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS
ISSN (Print)	0271-4302
ISSN (Electronic)	2379-447X

Conference

Conference	1999 IEEE International Symposium on Circuits and Systems, ISCAS 1999
Country/Territory	United States
City	Orlando
Period	30/05/99 → 2/06/99
Internet address	https://ieeexplore.ieee.org/xpl/conhome/6311/proceeding (Conference proceedings)

Access to Document

10.1109/ISCAS.1999.780122

Cite this

@inproceedings{a42354a6d027484fa7487fd827a9fdc8,

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 = "Wai-Kei Mak and Wong, \{D. F.\}",

year = "1999",

month = may,

day = "30",

doi = "10.1109/ISCAS.1999.780122",

language = "English",

isbn = "0780354710",

volume = "6",

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

publisher = "IEEE",

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

booktitle = "Proceedings of 1999 IEEE International Symposium on Circuits and Systems, ISCAS 1999",

address = "United States",

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

url = "https://ieeexplore.ieee.org/xpl/conhome/6311/proceeding",

}

Mak, W-K & Wong, DF 1999, A fast hypergraph minimum cut algorithm. in Proceedings of 1999 IEEE International Symposium on Circuits and Systems, ISCAS 1999. vol. 6, Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS, IEEE, pp. VI-170-VI-173, 1999 IEEE International Symposium on Circuits and Systems, ISCAS 1999, Orlando, Florida, United States, 30/05/99. https://doi.org/10.1109/ISCAS.1999.780122

A fast hypergraph minimum cut algorithm. / Mak, Wai-Kei; Wong, D. F.
Proceedings of 1999 IEEE International Symposium on Circuits and Systems, ISCAS 1999. Vol. 6 IEEE, 1999. p. VI-170-VI-173 (Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - A fast hypergraph minimum cut algorithm

AU - Mak, Wai-Kei

AU - Wong, D. F.

PY - 1999/5/30

Y1 - 1999/5/30

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 - https://www.scopus.com/pages/publications/0032678368

U2 - 10.1109/ISCAS.1999.780122

DO - 10.1109/ISCAS.1999.780122

M3 - Conference proceeding

AN - SCOPUS:0032678368

SN - 0780354710

VL - 6

T3 - Proceedings - IEEE International Symposium on Circuits and Systems, ISCAS

SP - VI-170-VI-173

BT - Proceedings of 1999 IEEE International Symposium on Circuits and Systems, ISCAS 1999

PB - IEEE

T2 - 1999 IEEE International Symposium on Circuits and Systems, ISCAS 1999

Y2 - 30 May 1999 through 2 June 1999

ER -

A fast hypergraph minimum cut algorithm

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this