{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T12:40:01Z","timestamp":1736167201937,"version":"3.32.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":30,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540528261"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0032052","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T06:05:31Z","timestamp":1134281131000},"page":"476-489","source":"Crossref","is-referenced-by-count":2,"title":["On parallelizing graph-partitioning heuristics"],"prefix":"10.1007","author":[{"given":"John E.","family":"Savage","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus G.","family":"Wloka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"11","key":"36_CR1","doi-asserted-by":"crossref","first-page":"1526","DOI":"10.1109\/12.42122","volume":"38","author":"G. E. Blelloch","year":"1989","unstructured":"G. E. Blelloch, \u201cScans as Primitive Parallel Operations,\u201d IEEE Trans. Computers, vol. 38, no. 11, pp. 1526\u20131538, 1989.","journal-title":"IEEE Trans. Computers"},{"issue":"4","key":"36_CR2","first-page":"343","volume":"1","author":"M. A. Breuer","year":"1977","unstructured":"M. A. Breuer, \u201cMin-Cut Placement,\u201d Design Automation and Fault-Tolerant Computing, vol. 1, no. 4, pp. 343\u2013362, Aug. 1977.","journal-title":"Design Automation and Fault-Tolerant Computing"},{"key":"36_CR3","doi-asserted-by":"crossref","unstructured":"T. Bui, S. Chaudhuri, F. T. Leighton and M. Sipser, \u201cGraph Bisection Algorithms with Good Average Case Behavior,\u201d in 25th Annual Symposium on Foundations of Computer Science, pp. 181\u2013192, 1984.","DOI":"10.1109\/SFCS.1984.715914"},{"key":"36_CR4","doi-asserted-by":"crossref","unstructured":"T. Bui, C. Heigham, C. Jones and T. Leighton, \u201cImproving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms,\u201d in 26th IEEE Design Automation Conf., pp. 775\u2013778, 1989.","DOI":"10.1145\/74382.74527"},{"key":"36_CR5","unstructured":"T. N. Bui, \u201cOn Bisecting Random Graphs,\u201d MS Thesis, MIT, February, 1983."},{"key":"36_CR6","doi-asserted-by":"crossref","unstructured":"E. C. Carlson and R. A. Rutenbar, \u201cMask Verification on the Connection Machine,\u201d in 25th IEEE Design Automation Conf., pp. 134\u2013140, 1988.","DOI":"10.1109\/DAC.1988.14748"},{"key":"36_CR7","unstructured":"A. Casotto and A. Sangiovanni-Vincentelli, \u201cPlacement of Standard Cells using Simulated Annealing on the Connection Machine,\u201d in ICCAD, pp. 350\u2013453, Nov. 1987."},{"key":"36_CR8","unstructured":"S.-C. Chang and J. Ja'Ja', \u201cOptimal Parallel Algorithms for River Routing,\u201d in Proc. 1988 International Conference on Parallel Processing, pp. 9\u201313, Sept. 1988."},{"key":"36_CR9","unstructured":"S.-C. Chang and J. Ja'Ja', \u201cParallel Algorithms for Channel Routing in the Knock-Knee Model,\u201d in Proc. 1988 International Conference on Parallel Processing, pp. 18\u201325, Sept. 1988."},{"issue":"3","key":"36_CR10","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1147\/rd.313.0391","volume":"31","author":"F. Darema","year":"1987","unstructured":"F. Darema, S. Kirkpatrick and V. A. Norton, \u201cParallel Algorithms for Chip Placement by Simulated Annealing,\u201d IBM Journal of Research and Development, vol. 31, no. 3, pp. 391\u2013401, May 1987.","journal-title":"IBM Journal of Research and Development"},{"issue":"1","key":"36_CR11","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1109\/TCAD.1985.1270101","volume":"CAD-4","author":"A. E. Dunlop","year":"1985","unstructured":"A. E. Dunlop and B. W. Kernighan, \u201cA Procedure for Placement of Standard-Cell VLSI Circuits,\u201d IEEE Trans. Computer-Aided Design, vol. CAD-4, no. 1, pp. 92\u201398, Jan. 1985.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"36_CR12","doi-asserted-by":"crossref","unstructured":"C. M. Fiduccia and R. M. Mattheyses, \u201cA Linear-Time Heuristic for Improving Network Partitions,\u201d in 19th IEEE Design Automation Conf., pp. 175\u2013181, 1982.","DOI":"10.1109\/DAC.1982.1585498"},{"key":"36_CR13","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979."},{"issue":"4","key":"36_CR14","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill, \u201cComputational Complexity of Probabilistic Turing Machines,\u201d SIAM J. Computing, vol. 6, no. 4, pp. 675\u2013695, 1977.","journal-title":"SIAM J. Computing"},{"issue":"1","key":"36_CR15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0020-0190(80)90117-9","volume":"10","author":"L. Goldschlager","year":"1980","unstructured":"L. Goldschlager, \u201cA Space Efficient Algorithm for the Monotone Planar Circuit Value Problem.,\u201d Information Processing Letters, vol. 10, no. 1, pp. 25\u201327, 1980.","journal-title":"Information Processing Letters"},{"issue":"2","key":"36_CR16","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"L. M. Goldschlager","year":"1977","unstructured":"L. M. Goldschlager, \u201cThe Monotone and Planar Circuit Value Problems,\u201d ACM Sigact News, vol. 9, no. 2, pp. 25\u201329, 1977.","journal-title":"ACM Sigact News"},{"key":"36_CR17","unstructured":"D. S. Johnson, C. A. Aragon, L. A. McGeoch and C. Schevon, \u201cOptimization by Simulated Annealing,\u201d in Operations Research, to appear, 1988."},{"key":"36_CR18","doi-asserted-by":"crossref","unstructured":"D. S. Johnson, C. H. Papadimitriou and M. Yannakakis, \u201cHow Easy is Local Search,\u201d in Journal of Computer and Systems Sciences, pp. 79\u2013100, 1988.","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"36_CR19","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 and S. Lin, \u201cAn Efficient Heuristic Procedure for Partitioning Graphs,\u201d AT&T Bell Labs. Tech. J., vol. 49, pp. 291\u2013307, Feb. 1970.","journal-title":"AT&T Bell Labs. Tech. J."},{"issue":"4598","key":"36_CR20","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirkpatrick","year":"1983","unstructured":"S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, \u201cOptimization by Simulated Annealing,\u201d Science, vol. 220, no. 4598, pp. 671\u2013680, May 1983.","journal-title":"Science"},{"issue":"5","key":"36_CR21","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1109\/TC.1984.1676460","volume":"33","author":"B. Krishnamurthy","year":"1984","unstructured":"B. Krishnamurthy, \u201cAn Improved Min-Cut Algorithm for Partitioning VLSI Networks,\u201d IEEE Trans. Computers, vol. 33, no. 5, pp. 438\u2013446, May 1984.","journal-title":"IEEE Trans. Computers"},{"issue":"1","key":"36_CR22","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner, \u201cThe Circuit Value Problem is Log Space Complete for P,\u201d ACM SIGACT News, vol. 7, no. 1, pp. 18\u201320, 1975.","journal-title":"ACM SIGACT News"},{"key":"36_CR23","doi-asserted-by":"crossref","unstructured":"J. Lam and J.-M. Delosme, \u201cSimulated Annealing: a Fast Heuristic for Some Generic Layout Problems,\u201d in ICCAD, pp. 510\u2013513, 1988.","DOI":"10.1109\/ICCAD.1988.122560"},{"key":"36_CR24","doi-asserted-by":"crossref","unstructured":"F. T. Leighton, \u201cA Layout Strategy for VLSI Which is Provably Good,\u201d in 14th Annual ACM Symposium on Theory of Computing, San Francisco, pp. 85\u201398, May 1982.","DOI":"10.1145\/800070.802180"},{"key":"36_CR25","unstructured":"J. E. Savage, The Complexity of Computing. John Wiley and Sons, 1976."},{"key":"36_CR26","unstructured":"J. E. Savage and M. G. Wloka, \u201cHeuristics for Parallel Graph Partitioning,\u201d Department of Computer Science, Brown University, Technical Report No. CS-89-41, Dec. 1989."},{"key":"36_CR27","series-title":"Lecture Notes in Computer Science","first-page":"288","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. E. Savage","year":"1988","unstructured":"J. E. Savage and M. G. Wloka, \u201cA Parallel Algorithm for Channel Routing,\u201d in Graph-Theoretic Concepts in Computer Science, no. 344. Amsterdam: Lecture Notes in Computer Science, Springer-Verlag, pp. 288\u2013301, June 1988."},{"key":"36_CR28","unstructured":"J. E. Savage and M. G. Wloka, \u201cParallel Constraint Graph Generation,\u201d in Proc. Decennial Caltech Conf. on VLSI, Cambridge, MA, pp. 241\u2013259, Mar. 1989."},{"key":"36_CR29","unstructured":"A. A. Sch\u00e4ffer and M. Yannakakis, \u201cSimple Local Search Problems That Are Hard to Solve,\u201d preprint, 1990."},{"key":"36_CR30","unstructured":"C. Wong and R. Fiebrich, \u201cSimulated Annealing-Based, Circuit Placement on the Connection Machine,\u201d in Proc. ICCD, pp. 78\u201382, Oct. 1987."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0032052","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T12:07:22Z","timestamp":1736165242000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0032052"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540528261"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/bfb0032052","relation":{},"subject":[]}}