{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,19]],"date-time":"2025-08-19T11:06:14Z","timestamp":1755601574836,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,5,5]],"date-time":"2016-05-05T00:00:00Z","timestamp":1462406400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2016,5,5]]},"abstract":"<jats:p>\n            The M\n            <jats:sc>inimum<\/jats:sc>\n            L\n            <jats:sc>inear<\/jats:sc>\n            A\n            <jats:sc>rrangement<\/jats:sc>\n            (MLA) problem involves embedding a given graph on the integer line so that the sum of the edge lengths of the embedded graph is minimized. Most layout problems are either intractable or not known to be tractable, parameterized by the\n            <jats:italic>treewidth<\/jats:italic>\n            of the input graph. We investigate MLA with respect to three parameters that provide more structure than treewidth. In particular, we give a factor (1 + \u03b5)-approximation algorithm for MLA parameterized by (\u03b5,\n            <jats:italic>k<\/jats:italic>\n            ), where\n            <jats:italic>k<\/jats:italic>\n            is the\n            <jats:italic>vertex cover number<\/jats:italic>\n            of the input graph. By a similar approach, we obtain two FPT algorithms that exactly solve MLA parameterized by, respectively, the\n            <jats:italic>max leaf<\/jats:italic>\n            and\n            <jats:italic>edge clique cover<\/jats:italic>\n            numbers of the input graph.\n          <\/jats:p>","DOI":"10.1145\/2898352","type":"journal-article","created":{"date-parts":[[2016,5,6]],"date-time":"2016-05-06T12:59:12Z","timestamp":1462539552000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Tractable Parameterizations for the Minimum Linear Arrangement Problem"],"prefix":"10.1145","volume":"8","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[{"name":"Bergen University, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beer-Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances","family":"Rosamond","sequence":"additional","affiliation":[{"name":"Bergen University, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadas","family":"Shachnai","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,5,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/080729256"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195229"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9312-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/120903518"},{"key":"e_1_2_1_5_1","volume-title":"Howard J. Karloff, and Satish Rao.","author":"Charikar Moses","year":"2006","unstructured":"Moses Charikar , Mohammad Taghi Hajiaghayi , Howard J. Karloff, and Satish Rao. 2006 . &ell;22 spreading metrics for vertex ordering problems. In SODA. 1018--1027. Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, and Satish Rao. 2006. &ell;22 spreading metrics for vertex ordering problems. In SODA. 1018--1027."},{"volume-title":"Graph Theory","author":"Diestel Reinhard","key":"e_1_2_1_6_1","unstructured":"Reinhard Diestel . 2000. Graph Theory . Springer-Verlag . Reinhard Diestel. 2000. Graph Theory. Springer-Verlag."},{"key":"e_1_2_1_7_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"2013","unstructured":"Rodney G. Downey and Michael R . Fellows . 2013 . Fundamentals of Parameterized Complexity. Springer . Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.07.009"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.11.026"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.04.008"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9167-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92182-0_28"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.05.008"},{"key":"e_1_2_1_14_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412236"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1330-6"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46078-8_21"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404010"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702413197"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2898352","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2898352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:29Z","timestamp":1750222589000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2898352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,5]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,5,5]]}},"alternative-id":["10.1145\/2898352"],"URL":"https:\/\/doi.org\/10.1145\/2898352","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2016,5,5]]},"assertion":[{"value":"2014-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}