{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:45Z","timestamp":1740109305616,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,5,31]],"date-time":"2021-05-31T00:00:00Z","timestamp":1622419200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,5,31]],"date-time":"2021-05-31T00:00:00Z","timestamp":1622419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1814613","CCF-1907937"],"award-info":[{"award-number":["CCF-1814613","CCF-1907937"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1910659","CCF-1910411"],"award-info":[{"award-number":["CCF-1910659","CCF-1910411"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Ministry of Research and Innovation","award":["PN-III-P4-ID-PCE-2016-0842"],"award-info":[{"award-number":["PN-III-P4-ID-PCE-2016-0842"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,8]]},"DOI":"10.1007\/s00453-021-00836-5","type":"journal-article","created":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T04:07:33Z","timestamp":1622520453000},"page":"2427-2468","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Maximum Binary Tree Problem"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3421-7238","authenticated-orcid":false,"given":"Karthekeyan","family":"Chandrasekaran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9673-4313","authenticated-orcid":false,"given":"Elena","family":"Grigorescu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6179-7613","authenticated-orcid":false,"given":"Gabriel","family":"Istrate","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1670-6011","authenticated-orcid":false,"given":"Shubhang","family":"Kulkarni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5719-6708","authenticated-orcid":false,"given":"Young-San","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1927-6085","authenticated-orcid":false,"given":"Minshen","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,31]]},"reference":[{"key":"836_CR1","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/j.endm.2005.05.035","volume":"19","author":"L Addario-Berry","year":"2005","unstructured":"Addario-Berry, L., Dalal, K., Reed, A.: Degree constrained subgraphs. Electron. Notes Discrete Math. 19, 257\u2013263 (2005)","journal-title":"Electron. Notes Discrete Math."},{"issue":"4","key":"836_CR2","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"836_CR3","doi-asserted-by":"crossref","unstructured":"Amini, O., Peleg, D., P\u00e9rennes, S., Sau, I., Saurabh, S.: Degree-constrained subgraph problems: hardness and approximation results. In: Approximation and Online Algorithms, pp. 29\u201342 (2009)","DOI":"10.1007\/978-3-540-93980-1_3"},{"key":"836_CR4","doi-asserted-by":"crossref","unstructured":"Amini, O., Sau, I., Saurabh, S.: Parameterized complexity of the smallest degree-constrained subgraph problem. In: Parameterized and Exact Computation, pp. 13\u201329 (2008)","DOI":"10.1007\/978-3-540-79723-4_4"},{"key":"836_CR5","doi-asserted-by":"crossref","unstructured":"Austrin, P., O\u2019Donnell, R., Wright, J.: A new point of NP-hardness for 2-to-1 label-cover. In: Proceedings of the 15th Annual International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX \u201912, pp.\u00a01\u201312 (2012)","DOI":"10.1007\/978-3-642-32512-0_1"},{"key":"836_CR6","unstructured":"Balogh, J., Bonchi\u015f, C., Dini\u015f, D., Istrate, G., Todinca, I.: On the heapability of finite partial orders. In: Discrete Mathematics and Theoretical Computer Science, vol. 22 (2020)"},{"issue":"4","key":"836_CR7","doi-asserted-by":"publisher","first-page":"1413","DOI":"10.1137\/080734340","volume":"39","author":"N Bansal","year":"2009","unstructured":"Bansal, N., Khandekar, R., Nagarajan, V.: Additive guarantees for degree-bounded directed network design. SIAM J. Comput. 39(4), 1413\u20131431 (2009)","journal-title":"SIAM J. Comput."},{"key":"836_CR8","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.jcss.2017.03.003","volume":"87","author":"A Bj\u00f6rklund","year":"2017","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci. 87, 119\u2013139 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"836_CR9","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Khanna, S.: Approximating longest directed paths and cycles. In: Languages and Programming, Automata, pp. 222\u2013233 (2004)","DOI":"10.1007\/978-3-540-27836-8_21"},{"issue":"2","key":"836_CR10","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1007\/s00453-015-9981-1","volume":"74","author":"A Bj\u00f6rklund","year":"2016","unstructured":"Bj\u00f6rklund, A., Kaski, P., Kowalik, \u0141: Constrained multilinear detection and generalized graph motifs. Algorithmica 74(2), 947\u2013967 (2016)","journal-title":"Algorithmica"},{"key":"836_CR11","doi-asserted-by":"crossref","unstructured":"Byers, J., Heeringa, B., Mitzenmacher, M., Zervas, G.: Heapable sequences and subseqeuences. In: Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, ANALCO \u201911, pp.\u00a033\u201344 (2011)","DOI":"10.1137\/1.9781611973013.4"},{"issue":"44","key":"836_CR12","doi-asserted-by":"publisher","first-page":"4489","DOI":"10.1016\/j.tcs.2009.07.029","volume":"410","author":"K Chaudhuri","year":"2009","unstructured":"Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: A push-relabel approximation algorithm for approximating the minimum-degree mst problem and its generalization to matroids. Theoret. Comput. Sci. 410(44), 4489\u20134503 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"836_CR13","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s00453-007-9115-5","volume":"55","author":"K Chaudhuri","year":"2009","unstructured":"Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: What would edmonds do? Augmenting paths and witnesses for degree-bounded MSTs. Algorithmica 55(1), 157\u2013189 (2009)","journal-title":"Algorithmica"},{"key":"836_CR14","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M.: Springer, Parameterized Algorithms (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"836_CR15","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90162-B","volume":"85","author":"P Erd\u00f6s","year":"1990","unstructured":"Erd\u00f6s, P., Faudree, R.J., Rousseau, C.C.: Subgraphs of minimal degree k. Discrete Math. 85, 53\u201358 (1990)","journal-title":"Discrete Math."},{"issue":"3","key":"836_CR16","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"M F\u00fcrer","year":"1994","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum-degree Steiner tree to within one of optimal. J. Algorithms 17(3), 409\u2013423 (1994)","journal-title":"J. Algorithms"},{"key":"836_CR17","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC \u201983, pp.\u00a0448\u2013456 (1983)","DOI":"10.1145\/800061.808776"},{"key":"836_CR18","volume-title":"Computers and Intractability","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability. W. H Freeman and Company, New York (1979)"},{"key":"836_CR19","doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: Minimum bounded degree spanning trees. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201906, pp.\u00a0273\u2013282 (2006)","DOI":"10.1109\/FOCS.2006.48"},{"issue":"4","key":"836_CR20","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1007\/s00453-011-9600-8","volume":"65","author":"S Guillemot","year":"2013","unstructured":"Guillemot, S., Sikora, F.: Finding and counting vertex-colored subtrees. Algorithmica 65(4), 828\u2013844 (2013)","journal-title":"Algorithmica"},{"key":"836_CR21","doi-asserted-by":"publisher","first-page":"413","DOI":"10.4086\/toc.2013.v009a011","volume":"9","author":"V Guruswami","year":"2013","unstructured":"Guruswami, V., Sinop, A.K.: Improved inapproximability results for maximum k-colorable subgraph. Theory Comput. 9, 413\u2013435 (2013)","journal-title":"Theory Comput."},{"key":"836_CR22","doi-asserted-by":"crossref","unstructured":"Istrate, G., Bonchi\u015f, C.: Heapability, interactive particle systems, partial orders: results and open problems. In: Proceedings of DCFS\u20192016, 18th International Conference on Descriptional Complexity of Formal Systems, Springer, pp.\u00a018\u201328 (2016)","DOI":"10.1007\/978-3-319-41114-9_2"},{"key":"836_CR23","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/BF02523689","volume":"18","author":"DR Karger","year":"1997","unstructured":"Karger, D.R., Motwani, R., Ramkumar, G.D.S.: On approximating the longest path in a graph. Algorithmica 18, 82\u201398 (1997)","journal-title":"Algorithmica"},{"issue":"5","key":"836_CR24","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1016\/j.jcss.2013.01.019","volume":"79","author":"R Khandekar","year":"2013","unstructured":"Khandekar, R., Kortsarz, G., Nutov, Z.: On some network design problems with degree constraints. J. Comput. Syst. Sci. 79(5), 725\u2013736 (2013)","journal-title":"J. Comput. Syst. Sci."},{"key":"836_CR25","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0020-0190(98)00173-2","volume":"68","author":"T Kloks","year":"1998","unstructured":"Kloks, T., Kratsch, D., M\u00fcller, H.: Bandwidth of chain graphs. Inf. Process. Lett. 68, 313\u2013315 (1998)","journal-title":"Inf. Process. Lett."},{"key":"836_CR26","doi-asserted-by":"publisher","first-page":"1783","DOI":"10.1137\/S009753970036917X","volume":"31","author":"J K\u00f6nemann","year":"2002","unstructured":"K\u00f6nemann, J., Ravi, R.: A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees. SIAM J. Comput. 31, 1783\u20131793 (2002)","journal-title":"SIAM J. Comput."},{"key":"836_CR27","doi-asserted-by":"crossref","unstructured":"Koutis, I..: Faster algebraic algorithms for path and packing problems. In: International Colloquium on Automata, Languages, and Programming, Springer, pp.\u00a0575\u2013586 (2008)","DOI":"10.1007\/978-3-540-70575-8_47"},{"key":"836_CR28","doi-asserted-by":"crossref","unstructured":"Koutis, I., Williams, R..: Limits and applications of group algebras for parameterized problems. In: International Colloquium on Automata, Languages, and Programming, Springer, pp.\u00a0653\u2013664 (2009)","DOI":"10.1007\/978-3-642-02927-1_54"},{"key":"836_CR29","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539702418048","volume":"34","author":"J K\u00f6nemann","year":"2005","unstructured":"K\u00f6nemann, J., Ravi, R.: Primal-dual meets local search: approximating msts with nonuniform degree bounds. SIAM J. Comput. 34, 763\u2013773 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"836_CR30","doi-asserted-by":"publisher","first-page":"1062","DOI":"10.1137\/070700620","volume":"39","author":"CL Lap","year":"2009","unstructured":"Lap, C.L., Joseph, N., Mohammad, S., Mohit, S.: Survivable network design with degree or order constraints. SIAM J. Comput. 39(3), 1062\u20131087 (2009)","journal-title":"SIAM J. Comput."},{"key":"836_CR31","doi-asserted-by":"crossref","unstructured":"Nederlof, J.: Fast polynomial-space algorithms using m\u00f6bius inversion: improving on steiner tree and related problems. In: International Colloquium on Automata, Languages, and Programming, Springer, pp.\u00a0713\u2013725 (2009)","DOI":"10.1007\/978-3-642-02927-1_59"},{"issue":"1","key":"836_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"836_CR33","unstructured":"Porfilio, J.: A combinatorial characterization of heapability. Master\u2019s Thesis, Williams College (2015)"},{"key":"836_CR34","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s00453-001-0038-2","volume":"31","author":"R Ravi","year":"2001","unstructured":"Ravi, R., Marathe, M., Ravi, S.S., Rosenkrantz, D.: Approximation algorithms for degree-constrained minimum-cost network-design problems. Algorithmica 31, 58\u201378 (2001)","journal-title":"Algorithmica"},{"issue":"1","key":"836_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629366","volume":"62","author":"M Singh","year":"2015","unstructured":"Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. J. ACM 62(1), 1\u201319 (2015)","journal-title":"J. ACM"},{"key":"836_CR36","unstructured":"Smith, J.: Minimum degree spanning trees on bipartite permutation graphs. Master\u2019s Thesis, University of Alberta (2011)"},{"issue":"3","key":"836_CR37","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J Spinrad","year":"1987","unstructured":"Spinrad, J., Brandst\u00e4dt, A., Stewart, L.: Bipartite permutation graphs. Discrete Appl. Math. 18(3), 279\u2013292 (1987)","journal-title":"Discrete Appl. Math."},{"key":"836_CR38","doi-asserted-by":"crossref","unstructured":"Uehara, R., Uno, Y.: Efficient algorithms for the longest path problem. In: Proceedings of the 15th International Conference on Algorithms and Computation, ISAAC \u201904, pp.\u00a0871\u2013883 (2004)","DOI":"10.1007\/978-3-540-30551-4_74"},{"issue":"6","key":"836_CR39","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length $$k$$ in $$O^*(2^k)$$ time. Inf. Process. Lett. 109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00836-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00836-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00836-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T14:04:33Z","timestamp":1626962673000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00836-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,31]]},"references-count":39,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["836"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00836-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,5,31]]},"assertion":[{"value":"10 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}