A fast hypergraph minimum cut algorithm

Wai-Kei Mak, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-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 languageEnglish
Title of host publicationProceedings of 1999 IEEE International Symposium on Circuits and Systems, ISCAS 1999
PublisherIEEE
PagesVI-170-VI-173
Number of pages4
Volume6
ISBN (Print)0780354710
DOIs
Publication statusPublished - 30 May 1999
Event1999 IEEE International Symposium on Circuits and Systems, ISCAS 1999 - Orlando, United States
Duration: 30 May 19992 Jun 1999
https://ieeexplore.ieee.org/xpl/conhome/6311/proceeding (Conference proceedings)

Publication series

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

Conference

Conference1999 IEEE International Symposium on Circuits and Systems, ISCAS 1999
Country/TerritoryUnited States
CityOrlando
Period30/05/992/06/99
Internet address

Scopus Subject Areas

  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A fast hypergraph minimum cut algorithm'. Together they form a unique fingerprint.

Cite this