{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T20:44:46Z","timestamp":1725914686475},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319687049"},{"type":"electronic","value":"9783319687056"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-68705-6_19","type":"book-chapter","created":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T06:06:22Z","timestamp":1509516382000},"page":"249-262","source":"Crossref","is-referenced-by-count":1,"title":["The Minimum Shared Edges Problem on\u00a0Grid-Like Graphs"],"prefix":"10.1007","author":[{"given":"Till","family":"Fluschnik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meike","family":"Hatzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steffen","family":"H\u00e4rtlein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hendrik","family":"Molter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henning","family":"Seidler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,2]]},"reference":[{"key":"19_CR1","unstructured":"Alanko, S., Crevals, S., Isopoussu, A., \u00d6sterg\u00e5rd, P.R.J., Pettersson, V.: Computing the domination number of grid graphs. Electron. J. Comb. 18(1), 18 p. (2011). http:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v18i1p141"},{"issue":"4","key":"19_CR2","doi-asserted-by":"crossref","first-page":"1288","DOI":"10.1007\/s10878-015-9950-2","volume":"32","author":"Y Aoki","year":"2016","unstructured":"Aoki, Y., Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Ito, T., Konrad, C., Zhou, X.: The minimum vulnerability problem on specific graph classes. J. Comb. Optim. 32(4), 1288\u20131304 (2016)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"19_CR3","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1007\/s00453-014-9927-z","volume":"70","author":"S Assadi","year":"2014","unstructured":"Assadi, S., Emamjomeh-Zadeh, E., Norouzi-Fard, A., Yazdanbod, S., Zarrabi-Zadeh, H.: The minimum vulnerability problem. Algorithmica 70(4), 718\u2013731 (2014)","journal-title":"Algorithmica"},{"key":"19_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/3-540-56402-0_41","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D Bhatia","year":"1993","unstructured":"Bhatia, D., Leighton, T., Makedon, F., Norton, C.H.: Improved algorithms for routing on two-dimensional grids. In: Mayr, E.W. (ed.) WG 1992. LNCS, vol. 657, pp. 114\u2013122. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-56402-0_41"},{"issue":"1","key":"19_CR5","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"19_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"19_CR7","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory. GTM, 4th edn. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-662-53622-3 . vol. 173","edition":"4"},{"key":"19_CR8","unstructured":"Fluschnik, T.: The parameterized complexity of finding paths with shared edges. Master\u2019s thesis, TU Berlin, March 2015. http:\/\/fpt.akt.tu-berlin.de\/publications\/theses\/MA-till-fluschnik.pdf"},{"key":"19_CR9","unstructured":"Fluschnik, T., Kratsch, S., Niedermeier, R., Sorge, M.: The parameterized complexity of the minimum shared edges problem. In: Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015. LIPIcs, vol. 45, pp. 448\u2013462. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)"},{"key":"19_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-662-55751-8_21","volume-title":"Fundamentals of Computation Theory","author":"T Fluschnik","year":"2017","unstructured":"Fluschnik, T., Morik, M., Sorge, M.: The complexity of routing with few collisions. In: Klasing, R., Zeitoun, M. (eds.) FCT 2017. LNCS, vol. 10472, pp. 257\u2013270. Springer, Berlin (2017). https:\/\/doi.org\/10.1007\/978-3-662-55751-8_21"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Fluschnik, T., Sorge, M.: The minimum shared edges problem on planar graphs. arXiv preprint arXiv:1602.01385 (2016)","DOI":"10.1007\/978-3-319-68705-6_19"},{"key":"19_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"7","key":"19_CR13","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1016\/j.dam.2009.02.007","volume":"158","author":"V Jel\u00ednek","year":"2010","unstructured":"Jel\u00ednek, V.: The rank-width of the square grid. Discrete Appl. Math. 158(7), 841\u2013850 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"19_CR14","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0020-0190(94)90049-3","volume":"49","author":"K Kanchanasut","year":"1994","unstructured":"Kanchanasut, K.: A shortest-path algorithm for Manhattan graphs. Inf. Process. Lett. 49(1), 21\u201325 (1994)","journal-title":"Inf. Process. Lett."},{"key":"19_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-662-53174-7_12","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"MM Kant\u00e9","year":"2016","unstructured":"Kant\u00e9, M.M., Moataz, F.Z., Mom\u00e8ge, B., Nisse, N.: Finding paths in grids with forbidden transitions. In: Mayr, E.W. (ed.) WG 2015. LNCS, vol. 9224, pp. 154\u2013168. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53174-7_12"},{"issue":"5","key":"19_CR16","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1109\/TCOM.1987.1096802","volume":"35","author":"N Maxemchuk","year":"1987","unstructured":"Maxemchuk, N.: Routing in the Manhattan street network. IEEE Trans. Commun. 35(5), 503\u2013512 (1987)","journal-title":"IEEE Trans. Commun."},{"issue":"4","key":"19_CR17","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1007\/s10878-012-9462-2","volume":"26","author":"MT Omran","year":"2013","unstructured":"Omran, M.T., Sack, J.R., Zarrabi-Zadeh, H.: Finding paths with minimum shared edges. J. Comb. Optim. 26(4), 709\u2013722 (2013)","journal-title":"J. Comb. Optim."},{"issue":"1\u20133","key":"19_CR18","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0166-218X(97)00116-9","volume":"83","author":"EA Varvarigos","year":"1998","unstructured":"Varvarigos, E.A.: Optimal communication algorithms for Manhattan street networks. Discrete Appl. Math. 83(1\u20133), 303\u2013326 (1998)","journal-title":"Discrete Appl. Math."},{"key":"19_CR19","unstructured":"Ye, Z.Q., Li, Y.M., Lu, H.Q., Zhou, X.: Finding paths with minimum shared edges in graphs with bounded treewidth. In: Proceedings of the 9th International Conference on Foundations of Computer Science, FCS 2013, pp. 40\u201346 (2013)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68705-6_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,6]],"date-time":"2022-08-06T01:10:55Z","timestamp":1659748255000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68705-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319687049","9783319687056"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68705-6_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}