{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T04:15:33Z","timestamp":1744085733394,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642329364"},{"type":"electronic","value":"9783642329371"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32937-1_51","type":"book-chapter","created":{"date-parts":[[2012,8,25]],"date-time":"2012-08-25T18:49:02Z","timestamp":1345920542000},"page":"510-518","source":"Crossref","is-referenced-by-count":3,"title":["A Spanning Tree-Based Encoding of the MAX CUT Problem for Evolutionary Search"],"prefix":"10.1007","author":[{"given":"Kisung","family":"Seo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Soohwan","family":"Hyun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong-Hyuk","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"51_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1112","DOI":"10.1007\/3-540-45105-6_120","volume-title":"Genetic and Evolutionary Computation - GECCO 2003","author":"Y.-H. Kim","year":"2003","unstructured":"Kim, Y.-H., Kwon, Y.-K., Moon, B.-R.: Problem-independent Schema Synthesis for Genetic Algorithms. In: Cant\u00fa-Paz, E., Foster, J.A., Deb, K., Davis, L., Roy, R., O\u2019Reilly, U.-M., Beyer, H.-G., Kendall, G., Wilson, S.W., Harman, M., Wegener, J., Dasgupta, D., Potter, M.A., Schultz, A., Dowsland, K.A., Jonoska, N., Miller, J., Standish, R.K. (eds.) GECCO 2003. LNCS, vol.\u00a02723, pp. 1112\u20131122. Springer, Heidelberg (2003)"},{"key":"51_CR2","doi-asserted-by":"crossref","unstructured":"Kim, Y.-H.: Linear transformation in pseudo-Boolean functions. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1117\u20131118 (2008)","DOI":"10.1145\/1389095.1389306"},{"issue":"4","key":"51_CR3","doi-asserted-by":"publisher","first-page":"184","DOI":"10.3837\/tiis.2008.04.002","volume":"2","author":"Y.-H. Kim","year":"2008","unstructured":"Kim, Y.-H., Yoon, Y.: Effect of changing the basis in genetic algorithms using binary encoding. KSII Transactions on Internet and Information Systems\u00a02(4), 184\u2013193 (2008)","journal-title":"KSII Transactions on Internet and Information Systems"},{"key":"51_CR4","doi-asserted-by":"crossref","unstructured":"Kim, Y.-H., Yoon, Y.: Representation and recombination over nonsingular binary matrices. In: Proceedings of the World Summit on Genetic and Evolutionary Computation, pp. 855\u2013858 (2009)","DOI":"10.1145\/1543834.1543959"},{"issue":"1-2","key":"51_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-9260(95)00008-4","volume":"19","author":"C.J. Alpert","year":"1995","unstructured":"Alpert, C.J., Kahng, A.B.: Recent directions in netlist partitioning: a survey. Integration, the VLSI Journal\u00a019(1-2), 1\u201381 (1995)","journal-title":"Integration, the VLSI Journal"},{"issue":"3","key":"51_CR6","doi-asserted-by":"publisher","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. Information Processing Letters\u00a042(3), 153\u2013159 (1992)","journal-title":"Information Processing Letters"},{"issue":"1","key":"51_CR7","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(92)90126-G","volume":"42","author":"L.H. Clark","year":"1992","unstructured":"Clark, L.H., Shahrokhi, F., Sz\u00e9kely, L.A.: A linear time algorithm for graph partition problems. Information Processing Letters\u00a042(1), 19\u201324 (1992)","journal-title":"Information Processing Letters"},{"issue":"4","key":"51_CR8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0020-0190(00)00189-7","volume":"79","author":"U. Feige","year":"2001","unstructured":"Feige, U., Karpinski, M., Langberg, M.: A note on approximating Max-Bisection on regular graphs. Information Processing Letters\u00a079(4), 181\u2013188 (2001)","journal-title":"Information Processing Letters"},{"key":"51_CR9","unstructured":"Fj\u00e4llstr\u00f6m, P.O.: Algorithms for graph partitioning: a survey. Linkoping Electronic Articles in Computer and Information Science\u00a03 (1998)"},{"issue":"9","key":"51_CR10","doi-asserted-by":"publisher","first-page":"1074","DOI":"10.1109\/43.159993","volume":"11","author":"L. Hagen","year":"1992","unstructured":"Hagen, L., Kahng, A.B.: New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems\u00a011(9), 1074\u20131085 (1992)","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"issue":"1","key":"51_CR11","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1023\/B:HEUR.0000019985.94952.eb","volume":"10","author":"Y.-H. Kim","year":"2004","unstructured":"Kim, Y.-H., Moon, B.-R.: Lock-gain based graph partitioning. Journal of Heuristics\u00a010(1), 37\u201357 (2004)","journal-title":"Journal of Heuristics"},{"issue":"2-3","key":"51_CR12","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0166-218X(94)00103-K","volume":"57","author":"L. Ku\u010dera","year":"1995","unstructured":"Ku\u010dera, L.: Expected complexity of graph partitioning problems. Discrete Applied Mathematics\u00a057(2-3), 193\u2013212 (1995)","journal-title":"Discrete Applied Mathematics"},{"key":"51_CR13","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0024-3795(88)90147-4","volume":"101","author":"D.L. Powers","year":"1988","unstructured":"Powers, D.L.: Graph partitioning by eigenvectors. Linear Algebra and its Applications\u00a0101, 121\u2013133 (1988)","journal-title":"Linear Algebra and its Applications"},{"issue":"5","key":"51_CR14","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0020-0190(94)00148-0","volume":"52","author":"J.-T. Yan","year":"1994","unstructured":"Yan, J.-T., Hsiao, P.-Y.: A fuzzy clustering algorithm for graph bisection. Information Processing Letters\u00a052(5), 259\u2013263 (1994)","journal-title":"Information Processing Letters"},{"key":"51_CR15","unstructured":"Antonio, S.M., Abraham, D., Juan, J.P., Ra\u00fal, C.: High-performance VNS for the max-cut problem using commodity graphics hardware. In: Proceedings of the 18th Mini Euro Conference on VNS (2005)"},{"issue":"4","key":"51_CR16","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1109\/43.494703","volume":"15","author":"J. Cong","year":"1996","unstructured":"Cong, J., Labio, W.J., Shivakumar, N.: Multiway VLSI circuit partitioning based on dual net representation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems\u00a015(4), 396\u2013409 (1996)","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"issue":"3","key":"51_CR17","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1137\/S0895479896312262","volume":"19","author":"S. Guattery","year":"1998","unstructured":"Guattery, S., Miller, G.L.: On the quality of spectral separators. SIAM Journal on Matrix Analysis and Applications\u00a019(3), 701\u2013719 (1998)","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"51_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/3-540-63138-0_23","volume-title":"Solving Irregularly Structured Problems in Parallel","author":"J. Michel","year":"1997","unstructured":"Michel, J., Pellegrini, F., Roman, J.: Unstructured Graph Partitioning for Sparse Linear System Solving. In: L\u00fcling, R., Bilardi, G., Ferreira, A., Rolim, J.D.P. (eds.) IRREGULAR 1997. LNCS, vol.\u00a01253, pp. 273\u2013286. Springer, Heidelberg (1997)"},{"key":"51_CR19","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1142\/S0129053394000160","volume":"6","author":"V. Venkatakrishnan","year":"1994","unstructured":"Venkatakrishnan, V.: Parallel computation of Ax and ATx. International Journal of High Speed Computing\u00a06, 325\u2013342 (1994)","journal-title":"International Journal of High Speed Computing"},{"key":"51_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11730095_1","volume-title":"Evolutionary Computation in Combinatorial Optimization","author":"M. Armbruster","year":"2006","unstructured":"Armbruster, M., F\u00fcgenschuh, M., Helmberg, C., Jetchev, N., Martin, A.: Hybrid Genetic Algorithm Within Branch-and-Cut for the Minimum Graph Bisection Problem. In: Gottlieb, J., Raidl, G.R. (eds.) EvoCOP 2006. LNCS, vol.\u00a03906, pp. 1\u201312. Springer, Heidelberg (2006)"},{"issue":"3","key":"51_CR21","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s10852-011-9154-4","volume":"10","author":"Y. Yoon","year":"2011","unstructured":"Yoon, Y., Kim, Y.-H., Moon, B.-R.: A note on edge-based graph partitioning and its linear algebraic structure. Journal of Mathematical Modelling and Algorithms\u00a010(3), 269\u2013276 (2011)","journal-title":"Journal of Mathematical Modelling and Algorithms"},{"key":"51_CR22","unstructured":"Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge University Press (1994)"},{"key":"51_CR23","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Graduate Texts in Mathematics, vol.\u00a0173. Springer, Heidelberg (2005)","edition":"3"},{"key":"51_CR24","doi-asserted-by":"crossref","unstructured":"Ford Jr., L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press (1962)","DOI":"10.1515\/9781400875184"},{"key":"51_CR25","first-page":"85","volume-title":"Reducibility Among Combinatorial Problems","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility Among Combinatorial Problems, pp. 85\u2013103. Plenum Press, New York (1972)"},{"issue":"3","key":"51_CR26","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theoretical Computer Science\u00a01(3), 237\u2013267 (1976)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"51_CR27","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"Sahni, S., Gonzalez, T.: P-complete approximation problems. Journal of the ACM\u00a023(3), 555\u2013565 (1976)","journal-title":"Journal of the ACM"},{"issue":"1","key":"51_CR28","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0012-365X(81)90023-6","volume":"34","author":"P.M.B. Vit\u00e1nyi","year":"1981","unstructured":"Vit\u00e1nyi, P.M.B.: How well can a graph be n-colored? Discrete Mathematics\u00a034(1), 69\u201380 (1981)","journal-title":"Discrete Mathematics"},{"key":"51_CR29","doi-asserted-by":"publisher","first-page":"519","DOI":"10.4153\/CJM-1982-036-8","volume":"34","author":"S. Poljak","year":"1982","unstructured":"Poljak, S., Tuza, Z.: A polynomial algorithm for constructing a large bipartite subgraph, with an application to a satisfiability problem. Canadian Journal of Mathematics\u00a034, 519\u2013524 (1982)","journal-title":"Canadian Journal of Mathematics"},{"key":"51_CR30","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1109\/12.67327","volume":"40","author":"D.J. Haglin","year":"1991","unstructured":"Haglin, D.J., Venkatesan, S.M.: Approximation and intractability results for the maximum cut problem and its variants. IEEE Trans. on Computer\u00a040, 110\u2013113 (1991)","journal-title":"IEEE Trans. on Computer"},{"key":"51_CR31","doi-asserted-by":"crossref","unstructured":"Hofmeister, T., Lefmann, H.: A combinatorial design approach to maxcut. In: Proceedings of the 13th Symposium on Theoretical Aspects of Computer Science (1995)","DOI":"10.1007\/3-540-60922-9_36"},{"issue":"6","key":"51_CR32","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the Association for Computing Machinery\u00a042(6), 1115\u20131145 (1995)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"51_CR33","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1006\/jpdc.1997.1381","volume":"46","author":"S. Homer","year":"1997","unstructured":"Homer, S., Peinado, M.: Design and Performance of Parallel and Distributed Approximation Algorithms for Maxcut. Journal of Parallel and Distributed Computing\u00a046, 48\u201361 (1997)","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"4598","key":"51_CR34","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science\u00a0220(4598), 671\u2013680 (1983)","journal-title":"Science"},{"key":"51_CR35","unstructured":"Kim, S.-H., Kim, Y.-H., Moon, B.-R.: A hybrid genetic algorithm for the MAX CUT problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 416\u2013423 (2001)"},{"key":"51_CR36","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F. Barahona","year":"1984","unstructured":"Barahona, F., Grotschel, M., Junger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Operational Research\u00a036, 493\u2013513 (1984)","journal-title":"Operational Research"},{"key":"51_CR37","first-page":"123","volume":"1","author":"R.Y. Pinter","year":"1984","unstructured":"Pinter, R.Y.: Optimal layer assignment for interconnect. Journal of VLSI Computing Systems\u00a01, 123\u2013137 (1984)","journal-title":"Journal of VLSI Computing Systems"},{"key":"51_CR38","unstructured":"Poljak, S., Tuza, Z.: Maximum cuts and largest bipartite subgraphs, vol. 20. American Mathematical Society (1993)"},{"key":"51_CR39","unstructured":"Boost Library, http:\/\/boost.org"},{"key":"51_CR40","unstructured":"Open Beagle, http:\/\/beagle.gel.ulaval.ca"},{"issue":"7","key":"51_CR41","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1109\/12.508322","volume":"45","author":"T.N. Bui","year":"1996","unstructured":"Bui, T.N., Moon, B.R.: Genetic algorithm and graph partitioning. IEEE Transactions on Computers\u00a045(7), 841\u2013855 (1996)","journal-title":"IEEE Transactions on Computers"}],"container-title":["Lecture Notes in Computer Science","Parallel Problem Solving from Nature - PPSN XII"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32937-1_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T08:42:11Z","timestamp":1744015331000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32937-1_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642329364","9783642329371"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32937-1_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}