{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T21:50:34Z","timestamp":1778795434005,"version":"3.51.4"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1987,6,1]],"date-time":"1987-06-01T00:00:00Z","timestamp":549504000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1987,6]]},"DOI":"10.1007\/bf02579448","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T21:10:40Z","timestamp":1174597840000},"page":"171-191","source":"Crossref","is-referenced-by-count":209,"title":["Graph bisection algorithms with good average case behavior"],"prefix":"10.1007","volume":"7","author":[{"given":"T. N.","family":"Bui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Chaudhuri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F. T.","family":"Leighton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Sipser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02579448_CR1","doi-asserted-by":"crossref","unstructured":"B. Baker, Approximation Algorithms for NP-complete Problems on Planar Graphs,FOCS 1983, 265\u2013273.","DOI":"10.1109\/SFCS.1983.7"},{"key":"BF02579448_CR2","doi-asserted-by":"crossref","unstructured":"E. R. BARNES, An Algorithm for Partitioning the Nodes of a Graph,IBM Technical Report RC8690, 1981.","DOI":"10.1109\/CDC.1981.269534"},{"key":"BF02579448_CR3","unstructured":"E. R. Barnes andA. J. Hoffman, Partitioning, Spectra and Linear Programming,IBM Research Report, (unknown date)."},{"key":"BF02579448_CR4","doi-asserted-by":"crossref","unstructured":"S. N. Bhatt andF. T. Leighton, A Framework for Solving VLSI Graph Layout Problems,Journal of Computer and System Sciences,28 (1984).","DOI":"10.1016\/0022-0000(84)90071-0"},{"key":"BF02579448_CR5","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","volume":"1","author":"B. Bollob\u00e1s","year":"1980","unstructured":"B. Bollob\u00e1s, A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs,European J. Combinatorics,1 (1980), 311\u2013316.","journal-title":"European J. Combinatorics"},{"key":"BF02579448_CR6","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF02579310","volume":"2","author":"B. Bollob\u00e1s","year":"1982","unstructured":"B. Bollob\u00e1s andW. Fernandez de la Vega, The Diameter of Random Regular Graphs,Combinatorica,2 (1982), 125\u2013134.","journal-title":"Combinatorica"},{"key":"BF02579448_CR7","first-page":"343","volume":"1","author":"M. A. Breuer","year":"1977","unstructured":"M. A. Breuer, Min-cut Placement,J. Design Aut. and Fault Tol. Comp.,1 (1977), 343\u2013362.","journal-title":"J. Design Aut. and Fault Tol. Comp."},{"key":"BF02579448_CR8","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1147\/rd.175.0420","volume":"17","author":"W. E. Donath","year":"1973","unstructured":"W. E. Donath andA. J. Hoffman, Lower Bounds for the Partitioning of Graphs,IBM J. Res. Develop.,17 (1973), 420\u2013425.","journal-title":"IBM J. Res. Develop."},{"key":"BF02579448_CR9","doi-asserted-by":"crossref","unstructured":"C. M. Fiduccia andR. M. Mattheyses, A Linear-Time Heuristic for Improving Network Partitions,Proceedings of the 19th Design Automation Conference, IEEE Computer Society Press. 1982, 175\u2013181.","DOI":"10.1109\/DAC.1982.1585498"},{"key":"BF02579448_CR10","volume-title":"Computers and Intractibility: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey andD. S. Johnson,Computers and Intractibility: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979."},{"key":"BF02579448_CR11","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson andL. Stockmeyer, Some Simplified NP-complete Graph Problems,Theoretical Computer Science,1 (1976), 237\u2013267.","journal-title":"Theoretical Computer Science"},{"key":"BF02579448_CR12","unstructured":"M. K. Goldberg andM. Burstein, Heuristic Improvement Techniques for Bisection of VLSI Networks,unpublished manuscript, 1984, Clarkson University."},{"key":"BF02579448_CR13","unstructured":"M. K. Goldberg andR. Gardner, On the Minimal Cut Problem,in: Progress in Graph Theory, (ed: J. A. Bondy and U.S.R. Murty), Academic Press, 1984, 295\u2013305."},{"key":"BF02579448_CR14","unstructured":"D. S. Johnson,personal communication."},{"key":"BF02579448_CR15","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","volume":"49","author":"B. W. Kernighan","year":"1970","unstructured":"B. W. Kernighan andS. Lin, An Efficient Heuristic Procedure for Partitioning Graphs,The Bell System Tech. J.,49 (1970), 291\u2013307.","journal-title":"The Bell System Tech. J."},{"key":"BF02579448_CR16","unstructured":"S. Kirkpatrick, C. D. Gelatt, Jr. andM. P. Vecchi, Optimization by Simulated Annealing,IBM Research Report RC 9355, April 1982, Yorktown Heights, New York."},{"key":"BF02579448_CR17","doi-asserted-by":"crossref","unstructured":"R. J. Lipton andR. E. Tarjan, Applications of a Planar Separator Theorem,Proceedings of the 18 th Symposium on the Foundation of Computer Science, (1977), 162\u2013170.","DOI":"10.1109\/SFCS.1977.6"},{"key":"BF02579448_CR18","first-page":"177","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton andR. E. Tarjan, A Separator Theorem for Planar Graphs,SIAM J. Computing,36 (1979), 177\u2013189.","journal-title":"SIAM J. Computing"},{"key":"BF02579448_CR19","unstructured":"R. M. Macgregor, On Partitioning a Graph: A Theoretical and Empirical Study,Ph. D. Thesis, University of California, Berkeley, 1978, also appeared as Technical Report UCB\/ERL M78\/14."},{"key":"BF02579448_CR20","doi-asserted-by":"crossref","unstructured":"R. L. Rivest, The \u201cPI\u201d (Placement and Interconnect) System,Proceedings of the 19 th Annual Design Automation Conference, IEEE 1982, 475\u2013481,Computer Society Press.","DOI":"10.1109\/DAC.1982.1585541"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579448.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579448\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579448","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T16:45:04Z","timestamp":1558197904000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579448"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,6]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1987,6]]}},"alternative-id":["BF02579448"],"URL":"https:\/\/doi.org\/10.1007\/bf02579448","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,6]]}}}