GRAPH BISECTION ALGORITHMS WITH GOOD AVERAGE CASE BEHAVIOR.

Thang Bui; Soma Chaudhuri; Tom Leighton; Mike Sipser

GRAPH BISECTION ALGORITHMS WITH GOOD AVERAGE CASE BEHAVIOR.

Thang Bui, Soma Chaudhuri, Tom Leighton, Mike Sipser

School of Science, Engineering & Technology (Harrisburg)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

24 Scopus citations

Abstract

A polynomial-time algorithm is described that, for every input graph, either outputs the minimum bisection of the graph or halts without output. It is shown that the algorithm chooses the former course with high probability for many natural classes of graphs. Experimental data for over 100 graphs are presented.

Original language	English (US)
Title of host publication	Annual Symposium on Foundations of Computer Science (Proceedings)
Publisher	IEEE
Pages	181-192
Number of pages	12
ISBN (Print)	081860591X
State	Published - 1984

Publication series

Name	Annual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)	0272-5428

All Science Journal Classification (ASJC) codes

Hardware and Architecture

Cite this

@inproceedings{3de366b63a4a44ea952ef9b908680e9b,

title = "GRAPH BISECTION ALGORITHMS WITH GOOD AVERAGE CASE BEHAVIOR.",

abstract = "A polynomial-time algorithm is described that, for every input graph, either outputs the minimum bisection of the graph or halts without output. It is shown that the algorithm chooses the former course with high probability for many natural classes of graphs. Experimental data for over 100 graphs are presented.",

author = "Thang Bui and Soma Chaudhuri and Tom Leighton and Mike Sipser",

year = "1984",

language = "English (US)",

isbn = "081860591X",

series = "Annual Symposium on Foundations of Computer Science (Proceedings)",

publisher = "IEEE",

pages = "181--192",

booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",

}

TY - GEN

T1 - GRAPH BISECTION ALGORITHMS WITH GOOD AVERAGE CASE BEHAVIOR.

AU - Bui, Thang

AU - Chaudhuri, Soma

AU - Leighton, Tom

AU - Sipser, Mike

PY - 1984

Y1 - 1984

N2 - A polynomial-time algorithm is described that, for every input graph, either outputs the minimum bisection of the graph or halts without output. It is shown that the algorithm chooses the former course with high probability for many natural classes of graphs. Experimental data for over 100 graphs are presented.

AB - A polynomial-time algorithm is described that, for every input graph, either outputs the minimum bisection of the graph or halts without output. It is shown that the algorithm chooses the former course with high probability for many natural classes of graphs. Experimental data for over 100 graphs are presented.

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

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

M3 - Conference contribution

AN - SCOPUS:0021555014

SN - 081860591X

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 181

EP - 192

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - IEEE

ER -

GRAPH BISECTION ALGORITHMS WITH GOOD AVERAGE CASE BEHAVIOR.

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this