{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T20:17:29Z","timestamp":1760645849572},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T00:00:00Z","timestamp":1308355200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2012,11]]},"DOI":"10.1007\/s10878-011-9406-2","type":"journal-article","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T02:13:28Z","timestamp":1308363208000},"page":"540-563","source":"Crossref","is-referenced-by-count":7,"title":["A branch-and-bound algorithm for the minimum cut linear arrangement problem"],"prefix":"10.1007","volume":"24","author":[{"given":"Gintaras","family":"Palubeckis","sequence":"first","affiliation":[]},{"given":"Dalius","family":"Rubliauskas","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,6,18]]},"reference":[{"key":"9406_CR1","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/s00440-004-0369-4","volume":"131","author":"N Berger","year":"2005","unstructured":"Berger N, Kenyon C, Mossel E, Peres Y (2005) Glauber dynamics on trees and hyperbolic graphs. Probab Theory Relat Fields 131:311\u2013340","journal-title":"Probab Theory Relat Fields"},{"key":"9406_CR2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/s000260050003","volume":"4","author":"SL Bezrukov","year":"2000","unstructured":"Bezrukov SL, Das SK, Els\u00e4sser R (2000) An edge-isoperimetric problem for powers of the Petersen graph. Ann Comb 4:153\u2013169","journal-title":"Ann Comb"},{"key":"9406_CR3","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/11604686_24","volume-title":"31st International workshop on graph-theoretic concepts in computer science (WG\u201905)","author":"G Blin","year":"2005","unstructured":"Blin G, Fertin G, Hermelin D, Vialette S (2005) Fixed-parameter algorithms for protein similarity search under mRNA structure constraints. In: 31st International workshop on graph-theoretic concepts in computer science (WG\u201905). LNCS, vol\u00a03787. Springer, Berlin, pp 271\u2013282"},{"key":"9406_CR4","first-page":"243","volume":"78","author":"L Brunetta","year":"1997","unstructured":"Brunetta L, Conforti M, Rinaldi G (1997) A branch-and-cut algorithm for the equicut problem. Math Program 78:243\u2013263","journal-title":"Math Program"},{"key":"9406_CR5","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz J, Petit J, Serna M (2002) A survey of graph layout problems. ACM Comput Surv 34:313\u2013356","journal-title":"ACM Comput Surv"},{"key":"9406_CR6","doi-asserted-by":"crossref","first-page":"245","DOI":"10.7155\/jgaa.00069","volume":"7","author":"HN Djidjev","year":"2003","unstructured":"Djidjev HN, Vrt\u2019o I (2003) Crossing numbers and cutwidths. J Graph Algorithms Appl 7:245\u2013251","journal-title":"J Graph Algorithms Appl"},{"key":"9406_CR7","unstructured":"G&G Graph Library (2009). http:\/\/bkocay.cs.umanitoba.ca\/g&g\/graphlib.html . Accessed 5 May 2009"},{"key":"9406_CR8","unstructured":"Gatto M, Jacob R, Nunkesser M (2006) Optimization of a railway hub-and-spoke system: routing and shunting. Technical report 477, ETH Zurich, Institute for Theoretical Computer Science"},{"key":"9406_CR9","first-page":"91","volume-title":"Proceedings of the 11th conference on information sciences and systems","author":"F Gavril","year":"1977","unstructured":"Gavril F (1977) Some NP-complete problems on graphs. In: Proceedings of the 11th conference on information sciences and systems. John Hopkins University, Baltimore, pp 91\u201395"},{"key":"9406_CR10","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F Glover","year":"1989","unstructured":"Glover F (1989) Tabu search\u2014part I. ORSA J Comput 1:190\u2013206","journal-title":"ORSA J Comput"},{"key":"9406_CR11","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0112012","volume":"12","author":"LH Harper","year":"1964","unstructured":"Harper LH (1964) Optimal assignments of numbers to vertices. SIAM J Appl Math 12:131\u2013135","journal-title":"SIAM J Appl Math"},{"key":"9406_CR12","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1287\/ijoc.12.3.177.12637","volume":"12","author":"SE Karisch","year":"2000","unstructured":"Karisch SE, Rendl F, Clausen J (2000) Solving graph bisection problems with semidefinite programming. INFORMS J Comput 12:177\u2013191","journal-title":"INFORMS J Comput"},{"key":"9406_CR13","first-page":"50","volume-title":"Proceedings of the 20th international conference on computers and their applications (CATA 2005)","author":"J Luttamaguzi","year":"2005","unstructured":"Luttamaguzi J, Pelsmajer M, Shen Z, Yang B (2005) Integer programming methods for several optimization problems in graph theory. In: Proceedings of the 20th international conference on computers and their applications (CATA 2005), New Orleans, LA, USA, pp 50\u201355"},{"key":"9406_CR14","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1007\/BFb0036931","volume-title":"Proceedings of the 10th colloquium on automata, languages and programming","author":"F Makedon","year":"1983","unstructured":"Makedon F, Sudborough IH (1983) Minimizing width in linear layouts. In: Proceedings of the 10th colloquium on automata, languages and programming. LNCS, vol\u00a0154. Springer, Berlin, pp 478\u2013490"},{"key":"9406_CR15","unstructured":"Mart\u00ed R, Pantrigo JJ, Duarte A, Pardo EG (2010) Branch and bound for the cutwidth minimization problem. Technical report, University of Valencia, Spain"},{"key":"9406_CR16","unstructured":"MathWorld: A Wolfram Web Resource (2009). http:\/\/mathworld.wolfram.com\/topics\/ArchimedeanGraphs.html . Accessed 5 May 2009"},{"key":"9406_CR17","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"B Monien","year":"1988","unstructured":"Monien B, Sudborough IH (1988) Min cut is NP-complete for edge weighted trees. Theor Comput Sci 58:209\u2013229","journal-title":"Theor Comput Sci"},{"key":"9406_CR18","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1142\/S0129626404001945","volume":"14","author":"B Monien","year":"2004","unstructured":"Monien B, Vrt\u2019o I (2004) Improved bounds on cutwidths of shuffle-exchange and de Bruijn graphs. Parallel Process Lett 14:361\u2013366","journal-title":"Parallel Process Lett"},{"key":"9406_CR19","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/s10955-006-9103-1","volume":"124","author":"A Montanari","year":"2006","unstructured":"Montanari A, Semerjian G (2006) On the dynamics of the glass transition on Bethe lattices. J Stat Phys 124:103\u2013189","journal-title":"J Stat Phys"},{"key":"9406_CR20","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1142\/S0129054103001637","volume":"14","author":"K Nakano","year":"2003","unstructured":"Nakano K (2003) Linear layout of generalized hypercubes. Int J Found Comput Sci 14:137\u2013156","journal-title":"Int J Found Comput Sci"},{"key":"9406_CR21","doi-asserted-by":"crossref","first-page":"279","DOI":"10.15388\/Informatica.2006.138","volume":"17","author":"G Palubeckis","year":"2006","unstructured":"Palubeckis G (2006) Iterated tabu search for the unconstrained binary quadratic optimization problem. Informatica 17:279\u2013296","journal-title":"Informatica"},{"key":"9406_CR22","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/j.amc.2006.11.090","volume":"189","author":"G Palubeckis","year":"2007","unstructured":"Palubeckis G (2007) Iterated tabu search for the maximum diversity problem. Appl Math Comput 189:371\u2013383","journal-title":"Appl Math Comput"},{"key":"9406_CR23","doi-asserted-by":"crossref","unstructured":"Pantrigo JJ, Mart\u00ed R, Duarte A, Pardo EG (2010) Scatter search for the cutwidth minimization problem. Technical report, University of Valencia, Spain","DOI":"10.1007\/s10479-011-0907-2"},{"key":"9406_CR24","unstructured":"PARTY Graph Collection (2009). http:\/\/wwwcs.uni-paderborn.de\/cs\/ag-monien\/RESEARCH\/PART\/graphs.html . Accessed 5 May 2009"},{"key":"9406_CR25","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1007\/3-540-60618-1_80","volume-title":"21st International workshop on graph-theoretic concepts in computer science (WG\u201995)","author":"J Rolim","year":"1995","unstructured":"Rolim J, S\u00fdkora O, Vrt\u2019o I (1995) Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes. In: 21st International workshop on graph-theoretic concepts in computer science (WG\u201995). LNCS, vol 1017. Springer, Berlin, pp 252\u2013264"},{"key":"9406_CR26","first-page":"209","volume-title":"Proceedings of the 11th IEEE\/ACM international workshop on logic&synthesis (IWLS-02)","author":"RS Shelar","year":"2002","unstructured":"Shelar RS, Sapatnekar SS (2002) Efficient layout synthesis algorithm for pass transistor logic circuits. In: Proceedings of the 11th IEEE\/ACM international workshop on logic&synthesis (IWLS-02), New Orleans, LA, USA, pp 209\u2013214"},{"key":"9406_CR27","first-page":"767","volume":"E82-A","author":"K Takagi","year":"1999","unstructured":"Takagi K, Takagi N (1999) Minimum cut linear arrangement of p\u2212q dags for VLSI layout of adder trees. IEICE Trans Fundam Electron Commun Comput Sci E82-A:767\u2013774","journal-title":"IEICE Trans Fundam Electron Commun Comput Sci"},{"key":"9406_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jalgor.2004.12.001","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos DM, Serna M, Bodlaender HL (2005a) Cutwidth I: a linear time fixed parameter algorithm. J\u00a0Algorithms 56:1\u201324","journal-title":"J\u00a0Algorithms"},{"key":"9406_CR29","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.jalgor.2004.12.003","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos DM, Serna M, Bodlaender HL (2005b) Cutwidth II: algorithms for partial w-trees of bounded degree. J Algorithms 56:25\u201349","journal-title":"J Algorithms"},{"key":"9406_CR30","unstructured":"Wikipedia (2009). http:\/\/en.wikipedia.org\/wiki\/Gray_graph . Accessed 5 May 2009"},{"key":"9406_CR31","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1145\/4221.4228","volume":"32","author":"M Yannakakis","year":"1985","unstructured":"Yannakakis M (1985) A polynomial algorithm for the min-cut linear arrangement of trees. J ACM 32:950\u2013988","journal-title":"J ACM"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-011-9406-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-011-9406-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-011-9406-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,20]],"date-time":"2020-06-20T09:45:57Z","timestamp":1592646357000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-011-9406-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,18]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,11]]}},"alternative-id":["9406"],"URL":"https:\/\/doi.org\/10.1007\/s10878-011-9406-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,18]]}}}