{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:59:11Z","timestamp":1780783151197,"version":"3.54.1"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032277312","type":"print"},{"value":"9783032277329","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-3-032-27732-9_12","type":"book-chapter","created":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:37Z","timestamp":1780780477000},"page":"161-174","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Algorithms for\u00a0Computing MAD Trees"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-2875-1945","authenticated-orcid":false,"given":"Tom-Lukas","family":"Breitkopf","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8499-0130","authenticated-orcid":false,"given":"Vincent","family":"Froese","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8473-9043","authenticated-orcid":false,"given":"Anton","family":"Herrmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7451-9401","authenticated-orcid":false,"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-3636-6571","authenticated-orcid":false,"given":"Camille","family":"Richer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,7]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","unstructured":"Abu-Affash, A.K., Carmi, P., Luwisch, O., Mitchell, J.S.B.: Geometric spanning trees minimizing the wiener index. Comput. Geom. Topol. 3(1), 2:1\u20132:15 (2024). https:\/\/doi.org\/10.57717\/CGT.V3I1.52","DOI":"10.57717\/CGT.V3I1.52"},{"issue":"1","key":"12_CR2","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0166-218X(97)00068-1","volume":"80","author":"CA Barefoot","year":"1997","unstructured":"Barefoot, C.A., Entringer, R.C., Sz\u00e9kely, L.A.: Extremal values for ratios of distances in trees. Discret. Appl. Math. 80(1), 37\u201356 (1997). https:\/\/doi.org\/10.1016\/S0166-218X(97)00068-1","journal-title":"Discret. Appl. Math."},{"key":"12_CR3","unstructured":"Breitkopf, T.L., Froese, V., Herrmann, A., Nichterlein, A., Richer, C.: Parameterized algorithms for computing MAD trees (2026). https:\/\/arxiv.org\/abs\/2603.29381"},{"key":"12_CR4","unstructured":"Burns, K., Entringer, R.C.: A graph-theoretic view of the united states postal service. In: Alavi, Y., Schwenk, A.J. (eds.) Graph Theory, Combinatorics, and Algorithms: Proceedings of the Seventh International Conference on the Theory and Applications of Graphs, pp. 323\u2013334. Wiley (1995)"},{"key":"12_CR5","doi-asserted-by":"publisher","unstructured":"Coudert, D., Ducoffe, G., Popa, A.: Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM Trans. Algorithms 15(3), 33:1\u201333:57 (2019). https:\/\/doi.org\/10.1145\/3310228","DOI":"10.1145\/3310228"},{"key":"12_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., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"1","key":"12_CR7","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0166-218X(02)00422-5","volume":"131","author":"E Dahlhaus","year":"2003","unstructured":"Dahlhaus, E., Dankelmann, P., Goddard, W., Swart, H.C.: MAD trees and distance-hereditary graphs. Discret. Appl. Math. 131(1), 151\u2013167 (2003). https:\/\/doi.org\/10.1016\/S0166-218X(02)00422-5","journal-title":"Discret. Appl. Math."},{"issue":"5","key":"12_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/J.IPL.2003.11.009","volume":"89","author":"E Dahlhaus","year":"2004","unstructured":"Dahlhaus, E., Dankelmann, P., Ravi, R.: A linear-time algorithm to compute a MAD tree of an interval graph. Inf. Process. Lett. 89(5), 255\u2013259 (2004). https:\/\/doi.org\/10.1016\/J.IPL.2003.11.009","journal-title":"Inf. Process. Lett."},{"key":"12_CR9","first-page":"93","volume":"32","author":"P Dankelmann","year":"2000","unstructured":"Dankelmann, P.: A note on MAD spanning trees. J. Comb. Math. Comb. Comput. 32, 93\u201396 (2000)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"3","key":"12_CR10","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1023\/A:1010767517079","volume":"66","author":"AA Dobrynin","year":"2001","unstructured":"Dobrynin, A.A., Entringer, R., Gutman, I.: Wiener index of trees: theory and applications. Acta Applicandae Mathematica 66(3), 211\u2013249 (2001). https:\/\/doi.org\/10.1023\/A:1010767517079","journal-title":"Acta Applicandae Mathematica"},{"key":"12_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"12_CR12","doi-asserted-by":"publisher","unstructured":"Drange, P.G., Dregi, M.S., van\u00a0\u2019t Hof, P.: On the computational complexity of vertex integrity and component order connectivity. Algorithmica 76(4), 1181\u20131202 (2016). https:\/\/doi.org\/10.1007\/S00453-016-0127-X","DOI":"10.1007\/S00453-016-0127-X"},{"issue":"4","key":"12_CR13","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1137\/0214064","volume":"14","author":"ES El-Mallah","year":"1985","unstructured":"El-Mallah, E.S., Colbourn, C.J.: Optimum communication spanning trees in series-parallel networks. SIAM J. Comput. 14(4), 915\u2013925 (1985). https:\/\/doi.org\/10.1137\/0214064","journal-title":"SIAM J. Comput."},{"key":"12_CR14","first-page":"65","volume":"24","author":"R Entringer","year":"1997","unstructured":"Entringer, R.: Distance in graphs: Trees. J. Comb. Math. Comb. Comput. 24, 65\u201384 (1997)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"12_CR15","doi-asserted-by":"publisher","unstructured":"Fischetti, M., Lancia, G., Serafini, P.: Exact algorithms for minimum routing cost trees. Networks 39(3), 161\u2013173 (2002). https:\/\/doi.org\/10.1002\/NET.10022","DOI":"10.1002\/NET.10022"},{"key":"12_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-319-03898-8_15","volume-title":"Parameterized and Exact Computation","author":"J Gajarsk\u00fd","year":"2013","unstructured":"Gajarsk\u00fd, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163\u2013176. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03898-8_15"},{"issue":"1","key":"12_CR17","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0166-218X(95)00038-S","volume":"65","author":"P Hansen","year":"1996","unstructured":"Hansen, P., Zheng, M.: Shortest shortest path trees of a network. Discret. Appl. Math. 65(1), 275\u2013284 (1996). https:\/\/doi.org\/10.1016\/0166-218X(95)00038-S","journal-title":"Discret. Appl. Math."},{"key":"12_CR18","doi-asserted-by":"publisher","unstructured":"Hassin, R., Tamir, A.: On the minimum diameter spanning tree problem. Inf. Process. Lett. 53(2), 109\u2013111 (1995). https:\/\/doi.org\/10.1016\/0020-0190(94)00183-Y","DOI":"10.1016\/0020-0190(94)00183-Y"},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-319-09620-9_11","volume-title":"Structural Information and Communication Complexity","author":"A Hochuli","year":"2014","unstructured":"Hochuli, A., Holzer, S., Wattenhofer, R.: Distributed approximation of minimum routing cost trees. In: Halld\u00f3rsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 121\u2013136. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-09620-9_11"},{"issue":"3","key":"12_CR20","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1137\/0203015","volume":"3","author":"TC Hu","year":"1974","unstructured":"Hu, T.C.: Optimum communication spanning trees. SIAM J. Comput. 3(3), 188\u2013195 (1974). https:\/\/doi.org\/10.1137\/0203015","journal-title":"SIAM J. Comput."},{"issue":"1","key":"12_CR21","first-page":"74","volume":"2","author":"B Jana","year":"2012","unstructured":"Jana, B., Mondal, S.: Computation of a minimum average distance tree on permutation graphs. Ann. Pure Appl. Math. 2(1), 74\u201385 (2012)","journal-title":"Ann. Pure Appl. Math."},{"issue":"3","key":"12_CR22","first-page":"384","volume":"6","author":"B Jana","year":"2015","unstructured":"Jana, B., Mondal, S., Pal, M.: Computation of a minimum average distance tree on circular-arc graphs. Int. J. Electron. Commun. Comput. Eng. 6(3), 384\u2013390 (2015)","journal-title":"Int. J. Electron. Commun. Comput. Eng."},{"issue":"4","key":"12_CR23","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1002\/net.3230080402","volume":"8","author":"DS Johnson","year":"1978","unstructured":"Johnson, D.S., Lenstra, J.K., Kan, A.H.G.R.: The complexity of the network design problem. Networks 8(4), 279\u2013285 (1978). https:\/\/doi.org\/10.1002\/net.3230080402","journal-title":"Networks"},{"key":"12_CR24","doi-asserted-by":"publisher","unstructured":"Kratsch, S., Nelles, F.: Efficient and adaptive parameterized algorithms on modular decompositions. In: Azar, Y., Bast, H., Herman, G. (eds.) 26th Annual European Symposium on Algorithms, ESA 2018, Helsinki, Finland, 20\u201322 August 2018. LIPIcs, vol.\u00a0112, pp. 55:1\u201355:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2018.55","DOI":"10.4230\/LIPICS.ESA.2018.55"},{"key":"12_CR25","unstructured":"Lokshtanov, D.: Parameterized integer quadratic programming: variables and coefficients. CoRR abs\/1511.00310 (2015). http:\/\/arxiv.org\/abs\/1511.00310"},{"key":"12_CR26","doi-asserted-by":"publisher","unstructured":"Lyaudet, L., Yonta, P.M., Tchuent\u00e9, M., Ndoundam, R.: Distance preserving subtrees in minimum average distance spanning trees. Discret. Math. Algorithms Appl. 5(3) (2013). https:\/\/doi.org\/10.1142\/S1793830913500109","DOI":"10.1142\/S1793830913500109"},{"key":"12_CR27","doi-asserted-by":"publisher","unstructured":"Masone, A., Nenni, M.E., Sforza, A., Sterle, C.: The minimum routing cost tree problem \u2013 state of the art and a core-node based heuristic algorithm. Soft Comput. 23(9), 2947\u20132957 (2019). https:\/\/doi.org\/10.1007\/S00500-018-3557-3","DOI":"10.1007\/S00500-018-3557-3"},{"issue":"2","key":"12_CR28","doi-asserted-by":"publisher","first-page":"598","DOI":"10.9734\/JSRR\/2013\/4661","volume":"2","author":"S Mondal","year":"2013","unstructured":"Mondal, S.: An efficient algorithm for computation of a minimum average distance tree on trapezoid graphs. J. Sci. Res. Rep. 2(2), 598\u2013611 (2013)","journal-title":"J. Sci. Res. Rep."},{"key":"12_CR29","unstructured":"Schmuck, N.S.: The wiener index of a graph (2010)"},{"key":"12_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1007\/978-3-540-70575-8_52","volume-title":"Automata, Languages and Programming","author":"M Tedder","year":"2008","unstructured":"Tedder, M., Corneil, D., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 634\u2013645. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_52"},{"issue":"1","key":"12_CR31","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1021\/ja01193a005","volume":"69","author":"H Wiener","year":"1947","unstructured":"Wiener, H.: Structural determination of paraffin boiling points. J. Am. Chem. Soc. 69(1), 17\u201320 (1947)","journal-title":"J. Am. Chem. Soc."},{"issue":"3","key":"12_CR32","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1137\/S009753979732253X","volume":"29","author":"BY Wu","year":"2000","unstructured":"Wu, B.Y., Lancia, G., Bafna, V., Chao, K.M., Ravi, R., Tang, C.Y.: A polynomial-time approximation scheme for minimum routing cost spanning trees. SIAM J. Comput. 29(3), 761\u2013778 (2000). https:\/\/doi.org\/10.1137\/S009753979732253X","journal-title":"SIAM J. Comput."},{"key":"12_CR33","doi-asserted-by":"publisher","unstructured":"Zehavi, M.: The k-leaf spanning tree problem admits a Klam value of 39. Eur. J. Comb. 68, 175\u2013203 (2018). https:\/\/doi.org\/10.1016\/J.EJC.2017.07.018","DOI":"10.1016\/J.EJC.2017.07.018"},{"key":"12_CR34","doi-asserted-by":"publisher","unstructured":"Zetina, C.A., Contreras, I.A., Fern\u00e1ndez, E., Luna-Mota, C.: Solving the optimum communication spanning tree problem. Eur. J. Oper. Res. 273(1), 108\u2013117 (2019). https:\/\/doi.org\/10.1016\/J.EJOR.2018.07.055","DOI":"10.1016\/J.EJOR.2018.07.055"}],"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-032-27732-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:40Z","timestamp":1780780480000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-27732-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032277312","9783032277329"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-27732-9_12","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":"7 June 2026","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":"Clermont-Ferrand","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","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":"8 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2026.limos.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}