{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:51Z","timestamp":1740122391170,"version":"3.37.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,9,11]],"date-time":"2015-09-11T00:00:00Z","timestamp":1441929600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,9,11]],"date-time":"2015-09-11T00:00:00Z","timestamp":1441929600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["25330003"],"award-info":[{"award-number":["25330003"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001840","name":"Icelandic Centre for Research","doi-asserted-by":"publisher","award":["120032011"],"award-info":[{"award-number":["120032011"]}],"id":[{"id":"10.13039\/501100001840","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001840","name":"Icelandic Centre for Research","doi-asserted-by":"publisher","award":["120032011"],"award-info":[{"award-number":["120032011"]}],"id":[{"id":"10.13039\/501100001840","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["CREST"],"award-info":[{"award-number":["CREST"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2016,11]]},"DOI":"10.1007\/s10878-015-9950-2","type":"journal-article","created":{"date-parts":[[2015,9,11]],"date-time":"2015-09-11T04:17:28Z","timestamp":1441945048000},"page":"1288-1304","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The minimum vulnerability problem on specific graph classes"],"prefix":"10.1007","volume":"32","author":[{"given":"Yusuke","family":"Aoki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bjarni V.","family":"Halld\u00f3rsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takehiro","family":"Ito","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Konrad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiao","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,11]]},"reference":[{"key":"9950_CR1","doi-asserted-by":"crossref","unstructured":"Aoki Y, Halld\u00f3rsson BV, Halld\u00f3rsson MM, Ito T, Konrad C, Zhou X (2014) The minimum vulnerability problem on graphs. In: Proc. COCOA 2014, LNCS 8881, pp. 299\u2013313","DOI":"10.1007\/978-3-319-12691-3_23"},{"key":"9950_CR2","doi-asserted-by":"crossref","unstructured":"Assadi S, Emamjomeh-Zadeh E, Norouzi-Fard A, Yazdanbod S, Zarrabi-Zadeh H (2012) The minimum vulnerability problem. In: Proc. ISAAC 2012, LNCS 7676, pp. 382\u2013391","DOI":"10.1007\/978-3-642-35261-4_41"},{"key":"9950_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender HL (1996) A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J Comput 25:1305\u20131317","journal-title":"SIAM J Comput"},{"key":"9950_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes: a survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt A, Le VB, Spinrad JP (1999) Graph classes: a survey. SIAM, Philadelphia"},{"key":"9950_CR5","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/1077464.1077470","volume":"1","author":"G Even","year":"2005","unstructured":"Even G, Kortsarz G, Slany W (2005) On network design problems: fixed cost flows and the covering Steiner problem. ACM Trans Algorithms 1:74\u2013101","journal-title":"ACM Trans Algorithms"},{"key":"9950_CR6","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco"},{"key":"9950_CR7","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril F (1974) The intersection graphs of subtrees in trees are exactly the chordal graphs. J Comb Theory Ser B 16:47\u201356","journal-title":"J Comb Theory Ser B"},{"key":"9950_CR8","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1145\/290179.290181","volume":"45","author":"AV Goldberg","year":"1998","unstructured":"Goldberg AV, Rao S (1998) Beyond the flow decomposition barrier. J ACM 45:783\u2013797","journal-title":"J ACM"},{"key":"9950_CR9","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1142\/S0129054199000137","volume":"10","author":"S Isobe","year":"1999","unstructured":"Isobe S, Zhou X, Nishizeki T (1999) A polynomial-time algorithm for finding total colorings of partial $$k$$-trees. Int J Found Comput Sci 10:171\u2013194","journal-title":"Int J Found Comput Sci"},{"key":"9950_CR10","first-page":"158","volume":"1998","author":"SO Krumke","year":"1998","unstructured":"Krumke SO, Noltemeier H, Schwarz S, Wirth H-C, Ravi R (1998) Flow improvement and network flows with fixed costs. Proc OR 1998:158\u2013167","journal-title":"Proc OR"},{"key":"9950_CR11","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0166-218X(01)00223-2","volume":"115","author":"T Nishizeki","year":"2001","unstructured":"Nishizeki T, Vygen J, Zhou X (2001) The edge-disjoint path problem is NP-complete for series-parallel graphs. Discret Appl Math 115:177\u2013186","journal-title":"Discret Appl Math"},{"key":"9950_CR12","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1007\/s10878-012-9462-2","volume":"26","author":"MT Omran","year":"2013","unstructured":"Omran MT, Sack J-R, Zarrabi-Zadeh H (2013) Finding paths with minimum shared edges. J Combin Optim 26:709\u2013722","journal-title":"J Combin Optim"},{"key":"9950_CR13","doi-asserted-by":"publisher","DOI":"10.1090\/fim\/019","volume-title":"Efficient graph representations","author":"JP Spinrad","year":"2003","unstructured":"Spinrad JP (2003) Efficient graph representations. American Mathematical Society, Providence"},{"key":"9950_CR14","unstructured":"Yang B, Yang M, Wang J, Zheng SQ (2005a) Minimum cost paths subject to minimum vulnerability for reliable communications. Proc ISPAN 2005:334\u2013339"},{"key":"9950_CR15","unstructured":"Yang M, Wang J, Qi X, Jiang Y (2005b) On finding the best partial multicast protection tree under dual-homing architecture. In: Proc IEEE HPSR, pp. 128\u2013132"},{"key":"9950_CR16","first-page":"40","volume":"2013","author":"ZQ Ye","year":"2013","unstructured":"Ye ZQ, Li YM, Lu HQ, Zhou X (2013) Finding paths with minimum shared edges in graphs with bounded treewidth. Proc FCS 2013:40\u201346","journal-title":"Proc FCS"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9950-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-015-9950-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9950-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9950-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T12:47:19Z","timestamp":1589719639000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-015-9950-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,11]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["9950"],"URL":"https:\/\/doi.org\/10.1007\/s10878-015-9950-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2015,9,11]]},"assertion":[{"value":"11 September 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}]}}