{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,13]],"date-time":"2026-11-13T10:18:04Z","timestamp":1794565084005,"version":"4.9.1"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319788241","type":"print"},{"value":"9783319788258","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-78825-8_27","type":"book-chapter","created":{"date-parts":[[2018,4,16]],"date-time":"2018-04-16T14:59:07Z","timestamp":1523890747000},"page":"327-340","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Linear Ordering Based MIP Formulations for the Vertex Separation or Pathwidth Problem"],"prefix":"10.1007","author":[{"given":"Sven","family":"Mallach","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,4,17]]},"reference":[{"issue":"2","key":"27_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebr. Discret. Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebr. Discret. Methods"},{"issue":"1","key":"27_CR2","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discret. Appl. Math. 23(1), 11\u201324 (1989)","journal-title":"Discret. Appl. Math."},{"key":"27_CR3","unstructured":"Biedl, T.C., Bl\u00e4sius, T., Niedermann, B., N\u00f6llenburg, M., Prutkin, R., Rutter, I.: Using ILP\/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings. CoRR, abs\/1308.6778v2 (2015)"},{"key":"27_CR4","unstructured":"Bodlaender, H., Gustedt, J., Telle, J.A.: Linear-time register allocation for a fixed number of registers. In: Proceedings of 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998, Philadelphia, PA, USA, pp. 574\u2013583. SIAM (1998)"},{"key":"27_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/3-540-19488-6_110","volume-title":"Automata, Languages and Programming","author":"HL Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Dynamic programming on graphs with bounded treewidth. In: Lepist\u00f6, T., Salomaa, A. (eds.) ICALP 1988. LNCS, vol. 317, pp. 105\u2013118. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/3-540-19488-6_110"},{"issue":"1\u20132","key":"27_CR6","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11(1\u20132), 1\u201323 (1993)","journal-title":"Acta Cybernetica"},{"issue":"1\u20132","key":"27_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209(1\u20132), 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"27_CR8","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/s00224-011-9312-0","volume":"50","author":"HL Bodlaender","year":"2012","unstructured":"Bodlaender, H.L., Fomin, F.V., Koster, A.M., Kratsch, D., Thilikos, D.M.: A note on exact algorithms for vertex ordering problems on graphs. Theory Comput. Syst. 50(3), 420\u2013432 (2012)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"27_CR9","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"issue":"3","key":"27_CR10","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2007","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3), 255 (2007)","journal-title":"Comput. J."},{"issue":"1","key":"27_CR11","doi-asserted-by":"publisher","first-page":"5","DOI":"10.7155\/jgaa.00117","volume":"10","author":"HL Bodlaender","year":"2006","unstructured":"Bodlaender, H.L., Wolle, T., Koster, A.M.C.A.: Contraction and treewidth lower bounds. J. Graph Algorithms Appl. 10(1), 5\u201349 (2006)","journal-title":"J. Graph Algorithms Appl."},{"key":"27_CR12","unstructured":"Coudert, D.: A note on integer linear programming formulations for linear ordering problems on graphs. Technical report hal-01271838, INRIA, February 2016"},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"1.3:1","DOI":"10.1145\/2851494","volume":"21","author":"D Coudert","year":"2016","unstructured":"Coudert, D., Mazauric, D., Nisse, N.: Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth. J. Exp. Algorithmics 21, 1.3:1\u20131.3:23 (2016)","journal-title":"J. Exp. Algorithmics"},{"issue":"1","key":"27_CR14","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1109\/TCAD.1987.1270248","volume":"6","author":"N Deo","year":"1987","unstructured":"Deo, N., Krishnamoorthy, M.S., Langston, M.A.: Exact and approximate solutions for the gate matrix layout problem. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 6(1), 79\u201384 (1987)","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"issue":"3","key":"27_CR15","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."},{"issue":"12","key":"27_CR16","doi-asserted-by":"publisher","first-page":"3247","DOI":"10.1016\/j.cor.2012.04.017","volume":"39","author":"A Duarte","year":"2012","unstructured":"Duarte, A., Escudero, L.F., Mart\u00ed, R., Mladenovic, N., Pantrigo, J.J., S\u00e1nchez-Oro, J.: Variable neighborhood search for the vertex separation problem. Comput. Oper. Res. 39(12), 3247\u20133255 (2012)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"27_CR17","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1006\/inco.1994.1064","volume":"113","author":"JA Ellis","year":"1994","unstructured":"Ellis, J.A., Sudborough, I.H., Turner, J.S.: The vertex separation and search number of a graph. Inf. Comput. 113(1), 50\u201379 (1994)","journal-title":"Inf. Comput."},{"key":"27_CR18","series-title":"Studies in Computational Intelligence","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/978-3-319-47054-2_44","volume-title":"Nature-Inspired Design of Hybrid Intelligent Systems","author":"HJ Fraire-Huacuja","year":"2017","unstructured":"Fraire-Huacuja, H.J., Castillo-Garc\u00eda, N., L\u00f3pez-Loc\u00e9s, M.C., Mart\u00ednez Flores, J.A., Pazos R., R.A., Gonz\u00e1lez Barbosa, J.J., Carpio Valadez, J.M.: Integer linear programming formulation and exact algorithm for computing pathwidth. In: Melin, P., Castillo, O., Kacprzyk, J. (eds.) Nature-Inspired Design of Hybrid Intelligent Systems. SCI, vol. 667, pp. 673\u2013686. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-47054-2_44"},{"issue":"1","key":"27_CR19","first-page":"31","volume":"6","author":"HJ Fraire Huacuja","year":"2015","unstructured":"Fraire Huacuja, H.J., Castillo-Garc\u00eda, N., Pazos Rangel, R.A., Mart\u00ednez Flores, J.A., Gonz\u00e1lez Barbosa, J.J., Carpio Valadez, J.M.: Two new exact methods for the vertex separation problem. IJCOPI 6(1), 31\u201341 (2015)","journal-title":"IJCOPI"},{"key":"27_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-319-44543-4_30","volume-title":"Combinatorial Algorithms","author":"M F\u00fcrer","year":"2016","unstructured":"F\u00fcrer, M.: Faster computation of path-width. In: M\u00e4kinen, V., Puglisi, S.J., Salmela, L. (eds.) IWOCA 2016. LNCS, vol. 9843, pp. 385\u2013396. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-44543-4_30"},{"key":"27_CR21","doi-asserted-by":"publisher","first-page":"2921","DOI":"10.1093\/comjnl\/bxv013","volume":"58","author":"F Gurski","year":"2015","unstructured":"Gurski, F.: Linear programming formulations for computing graph layout parameters. Comput. J. 58, 2921\u20132927 (2015)","journal-title":"Comput. J."},{"issue":"6","key":"27_CR22","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"NG Kinnersley","year":"1992","unstructured":"Kinnersley, N.G.: The vertex separation number of a graph equals its path-width. Inf. Process. Lett. 42(6), 345\u2013350 (1992)","journal-title":"Inf. Process. Lett."},{"key":"27_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-642-33293-7_18","volume-title":"Parameterized and Exact Computation","author":"K Kitsunai","year":"2012","unstructured":"Kitsunai, K., Kobayashi, Y., Komuro, K., Tamaki, H., Tano, T.: Computing directed pathwidth in $$O(1.89^{n})$$ time. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 182\u2013193. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33293-7_18"},{"key":"27_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/978-3-319-07959-2_33","volume-title":"Experimental Algorithms","author":"Y Kobayashi","year":"2014","unstructured":"Kobayashi, Y., Komuro, K., Tamaki, H.: Search space reduction through commitments in pathwidth computation: an experimental study. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 388\u2013399. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07959-2_33"},{"issue":"4","key":"27_CR25","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF00264496","volume":"16","author":"T Lengauer","year":"1981","unstructured":"Lengauer, T.: Black-white pebbles and graph separation. Acta Informatica 16(4), 465\u2013475 (1981)","journal-title":"Acta Informatica"},{"issue":"2","key":"27_CR26","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1016\/j.ejor.2007.02.004","volume":"186","author":"R Mart\u00ed","year":"2008","unstructured":"Mart\u00ed, R., Campos, V., Pi\u00f1ana, E.: A branch and bound algorithm for the matrix bandwidth minimization. Eur. J. Oper. Res. 186(2), 513\u2013528 (2008)","journal-title":"Eur. J. Oper. Res."},{"key":"27_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16729-4","volume-title":"The Linear Ordering Problem","author":"R Mart\u00ed","year":"2011","unstructured":"Mart\u00ed, R., Reinelt, G.: The Linear Ordering Problem. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-16729-4"},{"issue":"3","key":"27_CR28","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"issue":"12","key":"27_CR29","doi-asserted-by":"publisher","first-page":"1010","DOI":"10.1364\/JOCN.2.001010","volume":"2","author":"F Solano","year":"2010","unstructured":"Solano, F., Pi\u00f3ro, M.: Lightpath reconfiguration in WDM networks. IEEE\/OSA J. Opt. Commun. Netw. 2(12), 1010\u20131021 (2010)","journal-title":"IEEE\/OSA J. Opt. Commun. Netw."},{"key":"27_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-642-11269-0_27","volume-title":"Parameterized and Exact Computation","author":"K Suchan","year":"2009","unstructured":"Suchan, K., Villanger, Y.: Computing pathwidth faster than $$2^{n}$$. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 324\u2013335. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_27"},{"issue":"10","key":"27_CR31","doi-asserted-by":"publisher","first-page":"1822","DOI":"10.1016\/j.dam.2007.08.045","volume":"156","author":"B Yang","year":"2008","unstructured":"Yang, B., Cao, Y.: Digraph searching, directed vertex separation and directed pathwidth. Discret. Appl. Math. 156(10), 1822\u20131837 (2008)","journal-title":"Discret. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-78825-8_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T06:09:04Z","timestamp":1709791744000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-78825-8_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319788241","9783319788258"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-78825-8_27","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-319-78825-8","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"17 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Newcastle","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Australia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 July 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 July 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/carma.newcastle.edu.au\/meetings\/iwoca\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}