{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:24:17Z","timestamp":1726410257567},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_39","type":"book-chapter","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T23:22:47Z","timestamp":1376608967000},"page":"457-468","source":"Crossref","is-referenced-by-count":0,"title":["Tractable Parameterizations for the Minimum Linear Arrangement Problem"],"prefix":"10.1007","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances A.","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadas","family":"Shachnai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"39_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1137\/080729256","volume":"40","author":"C. Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., Mastrolilli, M., Svensson, O.: Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut. SIAM J. Comput.\u00a040(2), 567\u2013596 (2011)","journal-title":"SIAM J. Comput."},{"key":"39_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fellows, M.R., Hallett, M.T.: Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy. In: Proceedings of the 26th Annual Symposium on the Theory of Computing (STOC), pp. 449\u2013458 (1994)","DOI":"10.1145\/195058.195229"},{"issue":"3","key":"39_CR3","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/s00224-011-9312-0","volume":"50","author":"H.L. Bodlaender","year":"2012","unstructured":"Bodlaender, H.L., Fomin, F.V., Koster, A.M.C.A., Kratsch, D., Thilikos, D.M.: A note on exact algorithms for vertex ordering problems on graphs. Theory of Computing Systems\u00a050(3), 420\u2013432 (2012)","journal-title":"Theory of Computing Systems"},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"Charikar, M., Hajiaghayi, M.T., Karloff, H.J., Rao, S.: \n                  \n                    \n                  \n                  $\\ell^2_2$\n                 spreading metrics for vertex ordering problems. In: SODA, pp. 1018\u20131027 (2006)","DOI":"10.1145\/1109557.1109670"},{"issue":"1","key":"39_CR5","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.ipl.2006.07.009","volume":"101","author":"U. Feige","year":"2007","unstructured":"Feige, U., Lee, J.R.: An improved approximation ratio for the minimum linear arrangement problem. Inf. Process. Lett.\u00a0101(1), 26\u201329 (2007)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"39_CR6","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ic.2010.11.026","volume":"209","author":"M.R. Fellows","year":"2011","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F.A., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Information and Computation\u00a0209(2), 143\u2013153 (2011)","journal-title":"Information and Computation"},{"key":"39_CR7","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Shachnai, H.: Tractable parameterizations for the minimum linear arrangement problem, full version \n                  \n                    http:\/\/www.cs.technion.ac.il\/~hadas\/PUB\/MLA_FHRS.pdf\/"},{"issue":"3","key":"39_CR8","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","volume":"34","author":"M.R. Fellows","year":"2013","unstructured":"Fellows, M.R., Jansen, B.M.P., Rosamond, F.A.: Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. European Journal of Combinatorics\u00a034(3), 541\u2013566 (2013)","journal-title":"European Journal of Combinatorics"},{"issue":"4","key":"39_CR9","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1007\/s00224-009-9167-9","volume":"45","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F.A., Saurabh, S.: The complexity ecology of parameters: An illustration using bounded max leaf number. Theory Comput. Syst.\u00a045(4), 822\u2013848 (2009)","journal-title":"Theory Comput. Syst."},{"key":"39_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-540-92182-0_28","volume-title":"Algorithms and Computation","author":"M.R. Fellows","year":"2008","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 294\u2013305. Springer, Heidelberg (2008)"},{"issue":"17","key":"39_CR11","doi-asserted-by":"publisher","first-page":"3166","DOI":"10.1016\/j.dam.2008.05.008","volume":"156","author":"H. Fernau","year":"2008","unstructured":"Fernau, H.: Parameterized algorithmics for linear arrangement problems. Discrete Applied Mathematics\u00a0156(17), 3166\u20133177 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"39_CR12","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman (1979)"},{"key":"39_CR13","doi-asserted-by":"crossref","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Data reduction and exact algorithms for clique cover. ACM Journal of Experimental Algorithmics\u00a013 (2008)","DOI":"10.1145\/1412228.1412236"},{"issue":"3","key":"39_CR14","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00224-007-1330-6","volume":"41","author":"G. Gutin","year":"2007","unstructured":"Gutin, G., Rafiey, A., Szeider, S., Yeo, A.: The linear arrangement problem parameterized above guaranteed value. Theory Comput. Syst.\u00a041(3), 521\u2013538 (2007)","journal-title":"Theory Comput. Syst."},{"key":"39_CR15","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R. Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Mathematics of Operations Research\u00a012, 415\u2013440 (1987)","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"39_CR16","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/0404010","volume":"4","author":"D.J. Kleitman","year":"1991","unstructured":"Kleitman, D.J., West, D.B.: Spanning trees with many leaves. SIAM J. Discrete Math.\u00a04(1), 99\u2013106 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"39_CR17","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H. Lenstra","year":"1983","unstructured":"Lenstra, H.: Integer programming with a fixed number of variables. Mathematics of Operations Research\u00a08, 538\u2013548 (1983)","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"39_CR18","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1137\/S0097539702413197","volume":"34","author":"S. Rao","year":"2004","unstructured":"Rao, S., Richa, A.W.: New approximation techniques for some linear ordering problems. SIAM J. Comput.\u00a034(2), 388\u2013404 (2004)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T12:44:00Z","timestamp":1558010640000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}