{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:53Z","timestamp":1740109313836,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T00:00:00Z","timestamp":1661212800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T00:00:00Z","timestamp":1661212800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["W1230"],"award-info":[{"award-number":["W1230"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["RTG 2236 \"UnRAVeL\""],"award-info":[{"award-number":["RTG 2236 \"UnRAVeL\""]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Austrian Science Fund"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An instance of the non-preemptive tree packing problem consists of an undirected graph <jats:inline-formula><jats:alternatives><jats:tex-math>$$G=(V,E)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> together with a weight <jats:italic>w<\/jats:italic>(<jats:italic>e<\/jats:italic>) for every edge <jats:inline-formula><jats:alternatives><jats:tex-math>$$e\\in E$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>e<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The goal is to activate every edge <jats:italic>e<\/jats:italic> for some time interval of length <jats:italic>w<\/jats:italic>(<jats:italic>e<\/jats:italic>), such that the activated edges keep <jats:italic>G<\/jats:italic> connected for the longest possible overall time. We derive a variety of results on this problem. The problem is strongly NP-hard even on graphs of treewidth\u00a02, and it does not allow a polynomial time approximation scheme (unless P=NP). Furthermore, we discuss the performance of a simple greedy algorithm, and we construct and analyze a number of parameterized and exact algorithms.\n<\/jats:p>","DOI":"10.1007\/s00453-022-01026-7","type":"journal-article","created":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T09:03:05Z","timestamp":1661245385000},"page":"783-804","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Non-Preemptive Tree Packing"],"prefix":"10.1007","volume":"85","author":[{"given":"Stefan","family":"Lendl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerhard","family":"Woeginger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7139-4092","authenticated-orcid":false,"given":"Lasse","family":"Wulf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,23]]},"reference":[{"key":"1026_CR1","doi-asserted-by":"crossref","unstructured":"Adjiashvili, D., Bosio, S., Weismantel, R., Zenklusen, R.: Time-expanded packings. In: International Colloquium on Automata, Languages, and Programming. pp. 64\u201376. Springer (2014)","DOI":"10.1007\/978-3-662-43948-7_6"},{"key":"1026_CR2","first-page":"73","volume":"3","author":"T Akiyama","year":"1980","unstructured":"Akiyama, T., Nishizeki, T., Saito, N.: NP-completeness of the Hamiltonian cycle problem for bipartite graphs. Journal of Information processing 3, 73\u201376 (1980)","journal-title":"Journal of Information processing"},{"key":"1026_CR3","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1287\/moor.20.1.104","volume":"20","author":"F Barahona","year":"1995","unstructured":"Barahona, F.: Packing spanning trees. Math. Oper. Res. 20, 104\u2013115 (1995)","journal-title":"Math. Oper. Res."},{"issue":"1\u20132","key":"1026_CR4","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."},{"key":"1026_CR5","first-page":"774","volume":"50","author":"P Brucker","year":"1999","unstructured":"Brucker, P.: Scheduling algorithms. Journal-Operational Research Society 50, 774\u2013774 (1999)","journal-title":"Scheduling algorithms. Journal-Operational Research Society"},{"issue":"5","key":"1026_CR6","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1080\/17445760.2012.668546","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emergent Distrib. Syst."},{"key":"1026_CR7","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"1026_CR8","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/3828.3829","volume":"32","author":"WH Cunningham","year":"1985","unstructured":"Cunningham, W.H.: Optimal attack and reinforcement of a network. J. ACM 32, 549\u2013561 (1985)","journal-title":"J. ACM"},{"key":"1026_CR9","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, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms, vol. 5. Springer, Berlin (2015)"},{"key":"1026_CR10","doi-asserted-by":"publisher","first-page":"67","DOI":"10.6028\/jres.069B.004","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Minimum partition of a matroid into independent subsets. J. Res. Natl. Bur. Stand. 69, 67\u201372 (1965)","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"1026_CR11","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":"3","key":"1026_CR12","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1016\/j.jctb.2011.08.004","volume":"102","author":"J Van den Heuvel","year":"2012","unstructured":"Van den Heuvel, J., Thomass\u00e9, S.: Cyclic orderings and cyclic arboricity of matroids. Journal of Combinatorial Theory, Series B 102(3), 638\u2013646 (2012)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"1026_CR13","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moses, Y., Oshman, R.: Coordinated consensus in dynamic networks. In: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing. pp. 1\u201310 (2011)","DOI":"10.1145\/1993806.1993808"},{"key":"1026_CR14","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"36","author":"CSJA Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.S.J.A.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 36, 445\u2013450 (1961)","journal-title":"J. Lond. Math. Soc."},{"issue":"5","key":"1026_CR15","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1109\/JPROC.2018.2817461","volume":"106","author":"A Nedi\u0107","year":"2018","unstructured":"Nedi\u0107, A., Olshevsky, A., Rabbat, M.G.: Network topology and communication-computation tradeoffs in decentralized optimization. Proc. IEEE 106(5), 953\u2013976 (2018)","journal-title":"Proc. IEEE"},{"key":"1026_CR16","doi-asserted-by":"crossref","unstructured":"O\u2019Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Proceedings of the 2005 joint workshop on Foundations of mobile computing. pp. 104\u2013110 (2005)","DOI":"10.1145\/1080810.1080828"},{"key":"1026_CR17","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0012-365X(00)00066-2","volume":"230","author":"EM Palmer","year":"2001","unstructured":"Palmer, E.M.: On the spanning tree packing number of a graph: a survey. Discret. Math. 230, 13\u201321 (2001)","journal-title":"Discret. Math."},{"key":"1026_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-2361-4","volume-title":"Scheduling","author":"ML Pinedo","year":"2012","unstructured":"Pinedo, M.L.: Scheduling, vol. 29. Springer, Berlin (2012)"},{"key":"1026_CR19","unstructured":"West, D.B.: Introduction to Graph Theory. Pearson College Div (2000)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01026-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01026-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01026-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,3]],"date-time":"2023-03-03T15:06:23Z","timestamp":1677855983000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01026-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,23]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["1026"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01026-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,8,23]]},"assertion":[{"value":"15 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Stefan Lendl is a cofounder of s2 data & algorithms GmbH. Lasse Wulf has no conflict of interests to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}