{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T06:37:01Z","timestamp":1774334221656,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":24,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819571260","type":"print"},{"value":"9789819571277","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-981-95-7127-7_25","type":"book-chapter","created":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T10:07:10Z","timestamp":1770977230000},"page":"371-385","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Forcing a\u00a0Unique Minimum Spanning Tree and\u00a0a\u00a0Unique Shortest Path"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2815-5699","authenticated-orcid":false,"given":"Tatsuya","family":"Gima","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3244-6915","authenticated-orcid":false,"given":"Yasuaki","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0087-853X","authenticated-orcid":false,"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takumi","family":"Sato","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,14]]},"reference":[{"issue":"1\u20133","key":"25_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disc.2002.10.002","volume":"281","author":"P Adams","year":"2004","unstructured":"Adams, P., Mahdian, M., Mahmoodian, E.S.: On the forced matching numbers of bipartite graphs. Discret. Math. 281(1\u20133), 1\u201312 (2004)","journal-title":"Discret. Math."},{"key":"25_CR2","first-page":"147","volume":"30","author":"P Afshani","year":"2004","unstructured":"Afshani, P., Hatami, H., Mahmoodian, E.S.: On the spectrum of the forced matching number of graphs. Australas. J. Comb. 30, 147\u2013160 (2004)","journal-title":"Australas. J. Comb."},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"An, S., Chang, Y., Cho, K., Kwon, O., Lee, M., Oh, E., Shin, H.: Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs. In: 39th AAAI Conference on Artificial Intelligence, AAAI 2025, pp. 26886\u201326894 (2025)","DOI":"10.1609\/aaai.v39i25.34893"},{"issue":"2","key":"25_CR4","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"issue":"2","key":"25_CR5","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.orl.2006.03.005","volume":"35","author":"C Bentz","year":"2007","unstructured":"Bentz, C.: The maximum integer multiterminal flow problem in directed graphs. Oper. Res. Lett. 35(2), 195\u2013200 (2007)","journal-title":"Oper. Res. Lett."},{"issue":"6","key":"25_CR6","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"25_CR7","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1017\/S000497270004140X","volume":"1","author":"RA Brualdi","year":"1969","unstructured":"Brualdi, R.A.: Comments on bases in dependence structures. Bull. Aust. Math. Soc. 1(2), 161\u2013167 (1969)","journal-title":"Bull. Aust. Math. Soc."},{"issue":"1 &2","key":"25_CR8","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theoret. Comput. Sci. 109(1 &2), 49\u201382 (1993)","journal-title":"Theoret. Comput. Sci."},{"key":"25_CR9","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3_15","DOI":"10.1007\/978-3-319-21275-3_15"},{"key":"25_CR10","unstructured":"Demaine, E.D., Ma, F., Schvartzman, A., Waingarten, E., Aaronson, S.: The fewest clues problem. In: 8th International Conference on Fun with Algorithms, FUN 2016. LIPIcs, vol.\u00a049, pp. 12:1\u201312:12 (2016)"},{"issue":"2","key":"25_CR11","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1007\/s10878-015-9986-3","volume":"33","author":"K Deng","year":"2017","unstructured":"Deng, K., Zhang, H.: Anti-forcing spectra of perfect matchings of graphs. J. Comb. Optim. 33(2), 660\u2013680 (2017)","journal-title":"J. Comb. Optim."},{"key":"25_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. Freeman, W. H (1979)"},{"issue":"1\u20133","key":"25_CR13","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.disc.2004.08.026","volume":"293","author":"M Ghandehari","year":"2005","unstructured":"Ghandehari, M., Hatami, H., Mahmoodian, E.S.: On the size of the minimum critical set of a latin square. Discret. Math. 293(1\u20133), 121\u2013127 (2005)","journal-title":"Discret. Math."},{"key":"25_CR14","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01192587","volume":"6","author":"F Harary","year":"1991","unstructured":"Harary, F., Klein, D.J., \u017divkovi\u0107, T.P.: Graphical properties of polyhexes: perfect matching vector and forcing. J. Math. Chem. 6, 295\u2013306 (1991)","journal-title":"J. Math. Chem."},{"issue":"1","key":"25_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/050641594","volume":"37","author":"F Harary","year":"2007","unstructured":"Harary, F., Slany, W., Verbitsky, O.: On the computational complexity of the forcing chromatic number. SIAM J. Comput. 37(1), 1\u201319 (2007)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"25_CR16","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.dam.2005.03.004","volume":"149","author":"H Hatami","year":"2005","unstructured":"Hatami, H., Maserrat, H.: On the computational complexity of defining sets. Discret. Appl. Math. 149(1\u20133), 101\u2013110 (2005)","journal-title":"Discret. Appl. Math."},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Horiyama, T., Kobayashi, Y., Ono, H., Seto, K., Suzuki, R.: Theoretical aspects of generating instances with unique solutions: Pre-assignment models for unique vertex cover. In: Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, pp. 20726\u201320734 (2024)","DOI":"10.1609\/aaai.v38i18.30060"},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"Horiyama, T., Seto, K., Sakamoto, F., Suzuki, R.: Hardness of pre-assignment problem for unique minimum vertex cover on planar graphs with maximum degree 3. In: 25th International Symposium on Fundamentals of Computation Theory, FCT 2025. Lecture Notes in Computer Science, vol. 16106, pp. 238\u2013251 (2025)","DOI":"10.1007\/978-3-032-04700-7_18"},{"key":"25_CR19","unstructured":"Kimura, K., Kamehashi, T., Fujito, T.: The fewest clues problem of picross 3d. In: 9th International Conference on Fun with Algorithms, FUN 2018. LIPIcs, vol.\u00a0100, pp. 25:1\u201325:13 (2018)"},{"issue":"4","key":"25_CR20","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1002\/jcc.540080432","volume":"8","author":"DJ Klein","year":"1987","unstructured":"Klein, D.J., Randi\u0107, M.: Innate degree of freedom of a graph. J. Comput. Chem. 8(4), 516\u2013521 (1987)","journal-title":"J. Comput. Chem."},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc., 48\u201350 (1956)","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"Oxley, J.G.: Matroid theory. Oxford University Press, 2nd edn. (2011)","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001"},{"issue":"6","key":"25_CR23","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0020-0190(74)90003-9","volume":"2","author":"RE Tarjan","year":"1974","unstructured":"Tarjan, R.E.: A note on finding the bridges of a graph. Inf. Process. Lett. 2(6), 160\u2013161 (1974)","journal-title":"Inf. Process. Lett."},{"key":"25_CR24","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1016\/j.dam.2025.06.022","volume":"376","author":"Y Zhang","year":"2025","unstructured":"Zhang, Y., He, X., Liu, Q., Zhang, H.: Forcing, anti-forcing, global forcing and complete forcing on perfect matchings of graphs - a survey. Discret. Appl. Math. 376, 318\u2013347 (2025)","journal-title":"Discret. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-7127-7_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T04:14:32Z","timestamp":1774325672000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-7127-7_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9789819571260","9789819571277"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-7127-7_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"14 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Perugia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 March 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 March 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/mozart.diei.unipg.it\/walcom2026","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}