{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,23]],"date-time":"2025-05-23T05:24:52Z","timestamp":1747977892372,"version":"3.41.0"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319182629"},{"type":"electronic","value":"9783319182636"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-18263-6_15","type":"book-chapter","created":{"date-parts":[[2015,4,22]],"date-time":"2015-04-22T14:41:38Z","timestamp":1429713698000},"page":"168-180","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Minimum Linear Arrangement of Series-Parallel Graphs"],"prefix":"10.1007","author":[{"given":"Martina","family":"Eikel","sequence":"first","affiliation":[]},{"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Setzer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,23]]},"reference":[{"issue":"3","key":"15_CR1","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/0125042","volume":"25","author":"D Adolphson","year":"1973","unstructured":"Adolphson, D., Hu, T.C.: Optimal linear ordering. SIAM J. Appl. Math. 25(3), 403\u2013423 (1973)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"15_CR2","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1137\/0206002","volume":"6","author":"DL Adolphson","year":"1977","unstructured":"Adolphson, D.L.: Single machine job sequencing with precedence constraints. SIAM J. Comput. 6(1), 40\u201354 (1977)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Amb\u00fchl, C., Mastrolilli, M., Svensson, O.: Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling. In: Proceedings of FOCS, pp. 329\u2013337. IEEE Computer Society (2007)","key":"15_CR3","DOI":"10.1109\/FOCS.2007.40"},{"issue":"2","key":"15_CR4","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S Arora","year":"2009","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2), 5 (2009)","journal-title":"J. ACM"},{"key":"15_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/3-540-61680-2_62","volume-title":"Algorithms - ESA \u201996","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., de Fluiter, B.: Parallel algorithms for series parallel graphs. In: Diaz, J., Serna, M. (eds.) ESA 1996. LNCS, vol. 1136, pp. 277\u2013289. Springer, Heidelberg (1996)"},{"doi-asserted-by":"crossref","unstructured":"Charikar, M., Hajiaghayi, M.T., Karloff, H., Rao, S.: L22 spreading metrics for vertex ordering problems. In: Proceedings of SODA, pp. 1018\u20131027. Society for Industrial and Applied Mathematics, Philadelphia (2006)","key":"15_CR6","DOI":"10.1145\/1109557.1109670"},{"key":"15_CR7","first-page":"151","volume-title":"Selected Topics in Graph Theory","author":"FRK Chung","year":"1988","unstructured":"Chung, F.R.K.: Labelings of graphs. In: Beineke, L., Wilson, R. (eds.) Selected Topics in Graph Theory, vol. 3, pp. 151\u2013168. Academic Press, New York (1988)"},{"key":"15_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/11821069_24","volume-title":"Mathematical Foundations of Computer Science 2006","author":"J Cohen","year":"2006","unstructured":"Cohen, J., Fomin, F.V., Heggernes, P., Kratsch, D., Kucherov, G.: Optimal linear arrangement of interval graphs. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 267\u2013279. Springer, Heidelberg (2006)"},{"issue":"3","key":"15_CR9","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Petit, J., Serna, M.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313\u2013356 (2002)","journal-title":"ACM Comput. Surv."},{"doi-asserted-by":"crossref","unstructured":"Eikel, M., Scheideler, C., Setzer, A.: Minimum linear arrangement of series-parallel graphs (full paper). ArXiv e-prints, October 2014","key":"15_CR10","DOI":"10.1007\/978-3-319-18263-6_15"},{"issue":"1","key":"15_CR11","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0890-5401(92)90041-D","volume":"98","author":"D Eppstein","year":"1992","unstructured":"Eppstein, D.: Parallel recognition of series-parallel graphs. Inf. Comput. 98(1), 41\u201355 (1992)","journal-title":"Inf. Comput."},{"unstructured":"Even, S., Shiloach, Y.: NP-completeness of several arrangement problems. Department of Computer Science, Technion, Haifa, Israel, Technical Report 43 (1975)","key":"15_CR12"},{"issue":"1","key":"15_CR13","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. 101(1), 26\u201329 (2007)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"15_CR14","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0012-365X(99)00173-9","volume":"213","author":"P Fishburn","year":"2000","unstructured":"Fishburn, P., Tetali, P., Winkler, P.: Optimal linear arrangement of a rectangular grid. Discret. Math. 213(1\u20133), 123\u2013139 (2000)","journal-title":"Discret. Math."},{"issue":"3","key":"15_CR15","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1109\/31.1745","volume":"35","author":"GN Frederickson","year":"1988","unstructured":"Frederickson, G.N., Hambrusch, S.E.: Planar linear arrangements of outerplanar graphs. IEEE Trans. Circ. Syst. 35(3), 323\u2013333 (1988)","journal-title":"IEEE Trans. Circ. Syst."},{"issue":"3","key":"15_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"15_CR17","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F Hadlock","year":"1975","unstructured":"Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. 4(3), 221\u2013225 (1975)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"15_CR18","first-page":"131","volume":"12","author":"LH Harper","year":"1964","unstructured":"Harper, L.H.: Optimal assignments of numbers to vertices. J. SIAM 12(1), 131\u2013135 (1964)","journal-title":"J. SIAM"},{"issue":"3","key":"15_CR19","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0166-218X(83)90003-3","volume":"5","author":"T Kikuno","year":"1983","unstructured":"Kikuno, T., Yoshida, N., Kakuda, Y.: A linear algorithm for the domination number of a series-parallel graph. Discret. Appl. Math. 5(3), 299\u2013311 (1983)","journal-title":"Discret. Appl. Math."},{"key":"15_CR20","first-page":"601","volume":"28","author":"PA Macmahon","year":"1892","unstructured":"Macmahon, P.A.: The combination of resistances. Electrician 28, 601\u2013602 (1892)","journal-title":"Electrician"},{"key":"15_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/3-540-57899-4_66","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"K Nakano","year":"1994","unstructured":"Nakano, K.: Linear layouts of generalized hypercubes. In: van Leeuwen, J. (ed.) WG 1993. LNCS, vol. 790, pp. 364\u2013375. Springer, Heidelberg (1994)"},{"key":"15_CR22","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/996546.996554","volume":"8","author":"J Petit","year":"2003","unstructured":"Petit, J.: Experiments on the minimum linear arrangement problem. J. Exp. Algorithmics 8, 2\u20133 (2003)","journal-title":"J. Exp. Algorithmics"},{"issue":"105","key":"15_CR23","first-page":"177","volume":"3","author":"J Petit","year":"2013","unstructured":"Petit, J.: Addenda to the survey of layout problems. Bull. EATCS 3(105), 177\u2013201 (2013)","journal-title":"Bull. EATCS"},{"unstructured":"Rao, S., Richa, A.W.: New approximation techniques for some ordering problems. In: Proceedings of SODA, pp. 211\u2013218. Society for Industrial and Applied Mathematics, Philadelphia (1998)","key":"15_CR24"},{"issue":"1","key":"15_CR25","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1016\/j.amc.2008.04.051","volume":"203","author":"H Rostami","year":"2008","unstructured":"Rostami, H., Habibi, J.: Minimum linear arrangement of chord graphs. Appl. Math. Comput. 203(1), 358\u2013367 (2008)","journal-title":"Appl. Math. Comput."},{"unstructured":"Setzer, A.: The planar minimum linear arrangement problem is different from the minimum linear arrangement problem. ArXiv e-prints, September 2014","key":"15_CR26"},{"issue":"6","key":"15_CR27","doi-asserted-by":"publisher","first-page":"1773","DOI":"10.1137\/S0097539797331671","volume":"30","author":"F Shahrokhi","year":"2001","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L., Vrto, I.: On bipartite drawings and the linear arrangement problem. SIAM J. Comput. 30(6), 1773\u20131789 (2001)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"15_CR28","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K Takamizawa","year":"1982","unstructured":"Takamizawa, K., Nishizeki, T., Saito, N.: Linear-time computability of combinatorial problems on series-parallel graphs. J. ACM 29(3), 623\u2013641 (1982)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. In: Proceedings of STOC, pp. 1\u201312. ACM, New York (1979)","key":"15_CR29","DOI":"10.1145\/800135.804393"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18263-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T21:03:51Z","timestamp":1747947831000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-18263-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319182629","9783319182636"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18263-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"23 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}