{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T15:10:36Z","timestamp":1737385836783,"version":"3.33.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1998,6,1]],"date-time":"1998-06-01T00:00:00Z","timestamp":896659200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[1998,6]]},"DOI":"10.1007\/bf02684361","type":"journal-article","created":{"date-parts":[[2007,8,22]],"date-time":"2007-08-22T07:52:51Z","timestamp":1187769171000},"page":"121-132","source":"Crossref","is-referenced-by-count":3,"title":["An experimental evaluation of local search heuristics for graph partitioning"],"prefix":"10.1007","volume":"60","author":[{"given":"J. L.","family":"Ganley","sequence":"first","affiliation":[]},{"given":"L. S.","family":"Heath","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02684361_CR1","volume-title":"Introduction to probability and mathematical statistics","author":"L. J. Bain","year":"1992","unstructured":"Bain, L. J., Engelhardt, M.: Introduction to probability and mathematical statistics. Belmont: Duxbury Press 1992."},{"key":"BF02684361_CR2","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1002\/cpe.4330060203","volume":"6","author":"S. T. Barnard","year":"1994","unstructured":"Barnard, S. T., Simon, H. D.: Fast multilevel implementation of recursive bisection for partitioning unstructured problems. Concurrency6, 101\u2013117 (1994).","journal-title":"Concurrency"},{"key":"BF02684361_CR3","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1109\/TC.1987.1676942","volume":"36","author":"M. J. Berger","year":"1987","unstructured":"Berger, M. J., Bokhari, S. H.: A partitioning strategy for nonuniform problems on multiprocessors. IEEE Trans. Comput.36, 570\u2013580 (1987).","journal-title":"IEEE Trans. Comput."},{"key":"BF02684361_CR4","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/0743-7315(87)90018-9","volume":"4","author":"F. Berman","year":"1987","unstructured":"Berman, F., Snyder, L.: On mapping parallel algorithms into parallel architectures. J. Parallel Distrib. Comput.4, 439\u2013458 (1987).","journal-title":"J. Parallel Distrib. Comput."},{"key":"BF02684361_CR5","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"Sandeep. N. Bhatt","year":"1984","unstructured":"Bhatt, Sandeep. N., Thomson Leighton, F.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci.28, 300\u2013343 (1984).","journal-title":"J. Comput. Syst. Sci."},{"key":"BF02684361_CR6","volume-title":"Random graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"Bollob\u00e1s, B.: Random graphs. Orlando: Academic Press 1985."},{"key":"BF02684361_CR7","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0020-0190(92)90140-Q","volume":"42","author":"T. N. Bui","year":"1992","unstructured":"Bui, T. N., Jones, C.: Finding good approximate vertex and edge partitions is NP-hard. Inform. Proc. Lett.42, 153\u2013159 (1992).","journal-title":"Inform. Proc. Lett."},{"key":"BF02684361_CR8","unstructured":"Cohoon, J. P.: Personal communication (1992)."},{"key":"BF02684361_CR9","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1109\/43.75631","volume":"10","author":"J. P. Cohoon","year":"1991","unstructured":"Cohoon, J. P., Hedge, S. U., Martin, W. N., Richards, D.: Distributed genetic algorithms for the floorplan design problem. IEEE Trans. Comput. Aided Des.10, 483\u2013492 (1991).","journal-title":"IEEE Trans. Comput. Aided Des."},{"key":"BF02684361_CR10","doi-asserted-by":"crossref","first-page":"956","DOI":"10.1109\/TCAD.1987.1270337","volume":"6","author":"J. P. Cohoon","year":"1987","unstructured":"Cohoon, J. P., Paris, W. D.: Genetic placement. IEEE Trans. Comput. Aided Des.6, 956\u2013964 (1987).","journal-title":"IEEE Trans. Comput. Aided Des."},{"key":"BF02684361_CR11","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/3-540-55895-0_396","volume-title":"Parallel Processing: CONPAR 92\u2014VAPP V","author":"V. David","year":"1992","unstructured":"David, V., Fraboul, Ch., Rousselot, J. Y., Siron, P.: Partitioning and mapping communication graphs on a modular reconfigurable parallel architecture. In: Parallel Processing: CONPAR 92\u2014VAPP V, pp. 43\u201348. Berlin Heidelberg New York Tokyo: Springer 1992."},{"key":"BF02684361_CR12","first-page":"12","volume":"80","author":"P. J. Denning","year":"1992","unstructured":"Denning, P. J.: Genetic algorithms. Am. Sci.80, 12\u201314 (1992).","journal-title":"Am. Sci."},{"key":"BF02684361_CR13","doi-asserted-by":"crossref","unstructured":"Even, G., Naor, J., Rao, S., Schieber, B.: Divide-and-conquer approximation algorithms via spreading metrics. In: 36th IEEE Symp. on Foundations of Computer Science, pp. 62\u201371 (1995).","DOI":"10.1109\/SFCS.1995.492463"},{"key":"BF02684361_CR14","doi-asserted-by":"crossref","unstructured":"Fiduccia, C. M., Mattheyses, R. M.: A linear-time heuristic for improving network partitions. In: Proceedings of the 19th IEEE Design Automation Conference, pp. 175\u2013181 (1982).","DOI":"10.1109\/DAC.1982.1585498"},{"key":"BF02684361_CR15","doi-asserted-by":"crossref","first-page":"1109","DOI":"10.1109\/TC.1982.1675927","volume":"31","author":"M. A. Franklin","year":"1982","unstructured":"Franklin, M. A., Wann, D. F., Thomas, W. J.: Pin limitations and partitioning of VLSI interconnection networks. IEEE Trans. Comput.31, 1109\u20131116 (1982).","journal-title":"IEEE Trans. Comput."},{"key":"BF02684361_CR16","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/BF02276884","volume":"52","author":"J. L. Ganley","year":"1994","unstructured":"Ganley, J. L., Heath, L. S.: Heuristics for laying out information graphs. Computing52, 389\u2013405 (1994).","journal-title":"Computing"},{"key":"BF02684361_CR17","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1093\/comjnl\/37.7.641","volume":"37","author":"J. L. Ganley","year":"1994","unstructured":"Ganley, J. L., Heath, L. S.: Optimal and random partitions of random graphs. Comput. J.37, 641\u2013643 (1994).","journal-title":"Comput. J."},{"key":"BF02684361_CR18","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., Johnson, D. S.: Computers and intractability: a guide to the theory of NP-completeness. San Francisco: W. H. Freeman 1979."},{"key":"BF02684361_CR19","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F. Glover","year":"1989","unstructured":"Glover, F.: Tabu search\u2014part I. ORSA J. Comput.1, 190\u2013206 (1989).","journal-title":"ORSA J. Comput."},{"key":"BF02684361_CR20","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1287\/ijoc.2.1.4","volume":"2","author":"F. Glover","year":"1990","unstructured":"Glover, F.: Tabu search\u2014part II. ORSA J. Comput.2, 4\u201332 (1990).","journal-title":"ORSA J. Comput."},{"key":"BF02684361_CR21","volume-title":"Genetic algorithms in search, optimization, and machine learning","author":"D. E. Goldberg","year":"1989","unstructured":"Goldberg, D. E.: Genetic algorithms in search, optimization, and machine learning. Reading: Addison-Wesley 1989."},{"key":"BF02684361_CR22","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1145\/44483.44489","volume":"35","author":"L. S. Heath","year":"1988","unstructured":"Heath, L. S., Rosenberg, A. L., Smith, B. T.: The physical mapping problem for parallel architectures. J. Ass. Comput. Machin.35, 603\u2013631 (1988).","journal-title":"J. Ass. Comput. Machin."},{"key":"BF02684361_CR23","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1137\/0916028","volume":"16","author":"B. Hendrickson","year":"1995","unstructured":"Hendrickson, B., Leland, R.: An improved spectral graph partitioning algorithm for mapping parallel algorithms. SIAM J. Sci. Comput.16, 452\u2013469 (1995).","journal-title":"SIAM J. Sci. Comput."},{"key":"BF02684361_CR24","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1287\/opre.37.6.865","volume":"37","author":"D. S. Johnson","year":"1989","unstructured":"Johnson, D. S., Aragon, C. R., McGeoch, L. A., Schevon, C.: Optimization by simulated annealing; part I, graph partitioning. Oper. Res.37, 865\u2013892 (1989).","journal-title":"Oper. Res."},{"key":"BF02684361_CR25","unstructured":"Lavinus, J. W. (aka Ganley, J. L.): Heuristics for laying out information graphs. Master\u2019s thesis, Department of Computer Science, Virginia Polytechnic Institute and State University, 1992. Available as Technical Report ST92-01."},{"key":"BF02684361_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TC.1986.1676652","volume":"35","author":"D. I. Moldovan","year":"1986","unstructured":"Moldovan, D. I., Fortes, J. A. B.: Partitioning and mapping algorithms into fixed size systolic arrays. IEEE Trans. Comput.35, 1\u201312 (1986).","journal-title":"IEEE Trans. Comput."},{"volume-title":"Physical design automation of VLSI systems","year":"1988","key":"BF02684361_CR27","unstructured":"Preas, B. T., Lorenzetti, M. J. (eds.): Physical design automation of VLSI systems. Benjamin\/Cumming Publishing Company, Melno Park, California, 1988."},{"key":"BF02684361_CR28","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1109\/43.46801","volume":"9","author":"J. S. Rose","year":"1990","unstructured":"Rose, J. S., Klebsch, W., Wolf, J.: Temperature measurement and equilibrium dynamics of simulated annealing placement. IEEE Trans. Comput. Aided Des.9, 253\u2013259 (1990).","journal-title":"IEEE Trans. Comput. Aided Des."},{"key":"BF02684361_CR29","volume-title":"Graph separators, with applications","author":"A. L. Rosenberg","year":"1998","unstructured":"Rosenberg, A. L., Heath, L. S.: Graph separators, with applications. New York: Plenum Press 1998."},{"key":"BF02684361_CR30","volume-title":"Partitioning and scheduling parallel programs for multiprocessors","author":"Vivek. Sarkar","year":"1989","unstructured":"Sarkar, Vivek.: Partitioning and scheduling parallel programs for multiprocessors. Cambridge: MIT Press 1989."},{"key":"BF02684361_CR31","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/13310.13313","volume":"21","author":"Vivek. Sarkar","year":"1986","unstructured":"Sarkar, Vivek., Hennessy, John. L.: Compile-time partitioning and scheduling of parallel programs. SIGPLAN Notices21, 17\u201326 (1986).","journal-title":"SIGPLAN Notices"},{"key":"BF02684361_CR32","doi-asserted-by":"crossref","unstructured":"Shahookar, K., Mazumder, P.: A genetic approach to standard cell placement using metagenetic parameter optimization. IEEE Trans. Comput. Aided Des.9, 500\u2013511.","DOI":"10.1109\/43.55180"},{"key":"BF02684361_CR33","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-015-7744-1","volume-title":"Simulated annealing: theory and applications","author":"P. J. M. Laarhoven van","year":"1987","unstructured":"van Laarhoven, P. J. M., Aarts, E. H. L.: Simulated annealing: theory and applications. Boston: D. Reidel 1987."},{"key":"BF02684361_CR34","unstructured":"Varanelli, J. M., Cohoon, J. P.: Two-stage simulated annealing. In: Proceedings of the 4th ACM\/SIGDA Physical Design Workshop, pp. 1\u201310 (1993)."}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02684361.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02684361\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02684361","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T14:31:24Z","timestamp":1737383484000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02684361"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,6]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,6]]}},"alternative-id":["BF02684361"],"URL":"https:\/\/doi.org\/10.1007\/bf02684361","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"type":"print","value":"0010-485X"},{"type":"electronic","value":"1436-5057"}],"subject":[],"published":{"date-parts":[[1998,6]]}}}