{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,30]],"date-time":"2022-10-30T04:41:46Z","timestamp":1667104906549},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T00:00:00Z","timestamp":1662336000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T00:00:00Z","timestamp":1662336000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"GRFP","award":["DGE-1650044"],"award-info":[{"award-number":["DGE-1650044"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s10878-022-00897-4","type":"journal-article","created":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T03:14:23Z","timestamp":1662347663000},"page":"3419-3445","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Algorithms for maximum internal spanning tree problem for some graph classes"],"prefix":"10.1007","volume":"44","author":[{"given":"Gopika","family":"Sharma","sequence":"first","affiliation":[]},{"given":"Arti","family":"Pandey","sequence":"additional","affiliation":[]},{"given":"Michael C.","family":"Wigal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,5]]},"reference":[{"issue":"1","key":"897_CR1","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s00453-011-9575-5","volume":"65","author":"D Binkele-Raible","year":"2013","unstructured":"Binkele-Raible D, Fernau H, Gaspers S et al (2013) Exact and parameterized algorithms for max internal spanning tree. Algorithmica 65(1):95\u2013128","journal-title":"Algorithmica"},{"issue":"3","key":"897_CR2","doi-asserted-by":"publisher","first-page":"955","DOI":"10.1007\/s10878-017-0245-7","volume":"35","author":"ZZ Chen","year":"2018","unstructured":"Chen ZZ, Harada Y, Guo F et al (2018) An approximation algorithm for maximum internal spanning tree. J Comb Optim 35(3):955\u2013979","journal-title":"J Comb Optim"},{"issue":"7","key":"897_CR3","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1016\/j.jcss.2010.01.001","volume":"76","author":"N Cohen","year":"2010","unstructured":"Cohen N, Fomin FV, Gutin G et al (2010) Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. J Comput Syst Sci 76(7):650\u2013662","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"897_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2012.03.004","volume":"79","author":"FV Fomin","year":"2013","unstructured":"Fomin FV, Gaspers S, Saurabh S et al (2013) A linear vertex kernel for maximum internal spanning tree. J Comput Syst Sci 79(1):1\u20136","journal-title":"J Comput Syst Sci"},{"key":"897_CR5","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability, vol 174. freeman San Francisco"},{"issue":"1\u20132","key":"897_CR6","first-page":"87","volume":"14","author":"P Heggernes","year":"2007","unstructured":"Heggernes P, Kratsch D (2007) Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nord J Comput 14(1\u20132):87\u2013108","journal-title":"Nord J Comput"},{"issue":"3","key":"897_CR7","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.1137\/110830514","volume":"26","author":"P Heggernes","year":"2012","unstructured":"Heggernes P, Van\u2019t Hof P, Lokshtanov D et al (2012) Computing the cutwidth of bipartite permutation graphs in linear time. SIAM J Discret Math 26(3):1008\u20131021","journal-title":"SIAM J Discret Math"},{"issue":"2","key":"897_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0095-8956(78)90013-8","volume":"24","author":"HA Jung","year":"1978","unstructured":"Jung HA (1978) On a class of posets and the corresponding comparability graphs. J Comb Theory Series B 24(2):125\u2013133","journal-title":"J Comb Theory Series B"},{"issue":"4","key":"897_CR9","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1007\/s00453-013-9827-7","volume":"71","author":"M Knauer","year":"2015","unstructured":"Knauer M, Spoerhase J (2015) Better approximation algorithms for the maximum internal spanning tree problem. Algorithmica 71(4):797\u2013811","journal-title":"Algorithmica"},{"issue":"1","key":"897_CR10","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0020-0190(93)90191-B","volume":"46","author":"TH Lai","year":"1993","unstructured":"Lai TH, Wei SS (1993) The edge hamiltonian path problem is np-complete for bipartite graphs. Inf Process Lett 46(1):21\u201326","journal-title":"Inf Process Lett"},{"issue":"1","key":"897_CR11","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0166-218X(96)00014-5","volume":"74","author":"TH Lai","year":"1997","unstructured":"Lai TH, Wei SS (1997) Bipartite permutation graphs with application to the minimum buffer size problem. Discret Appl Math 74(1):33\u201355","journal-title":"Discret Appl Math"},{"key":"897_CR12","unstructured":"Lerchs H (1972) On the clique-kernel structure of graphs. Dept of Computer Science, University of Toronto 1"},{"key":"897_CR13","doi-asserted-by":"crossref","unstructured":"Li W, Wang J, Chen J, et\u00a0al (2015) A 2k-vertex kernel for maximum internal spanning tree. In: Workshop on algorithms and data structures, Springer, pp 495\u2013505","DOI":"10.1007\/978-3-319-21840-3_41"},{"key":"897_CR14","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.ic.2016.11.003","volume":"252","author":"W Li","year":"2017","unstructured":"Li W, Cao Y, Chen J et al (2017) Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree. Inf Comput 252:187\u2013200","journal-title":"Inf Comput"},{"key":"897_CR15","doi-asserted-by":"crossref","unstructured":"Li X, Zhu D (2014) Approximating the maximum internal spanning tree problem via a maximum path-cycle cover. In: International symposium on algorithms and computation, Springer, pp 467\u2013478","DOI":"10.1007\/978-3-319-13075-0_37"},{"key":"897_CR16","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2017.09.017","volume":"734","author":"X Li","year":"2018","unstructured":"Li X, Feng H, Jiang H et al (2018) Solving the maximum internal spanning tree problem on interval graphs in polynomial time. Theor Comput Sci 734:32\u201337","journal-title":"Theor Comput Sci"},{"key":"897_CR17","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.jcss.2021.01.001","volume":"118","author":"X Li","year":"2021","unstructured":"Li X, Zhu D, Wang L (2021) A 4\/3-approximation algorithm for the maximum internal spanning tree problem. J Comput Syst Sci 118:131\u2013140","journal-title":"J Comput Syst Sci"},{"issue":"8","key":"897_CR18","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0898-1221(95)00139-P","volume":"30","author":"R Lin","year":"1995","unstructured":"Lin R, Olariu S, Pruesse G (1995) An optimal path cover algorithm for cographs. Comput Math Appl 30(8):75\u201383","journal-title":"Comput Math Appl"},{"key":"897_CR19","unstructured":"Lu HI, Ravi R (1992) The power of local optimization: Approximation algorithms for maximum-leaf spanning tree. In: Proceedings of the annual allerton conference on communication control and computing, University of Illinois, pp 533\u2013533"},{"issue":"1\u20133","key":"897_CR20","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"H M\u00fcller","year":"1996","unstructured":"M\u00fcller H (1996) Hamiltonian circuits in chordal bipartite graphs. Discret Math 156(1\u20133):291\u2013298","journal-title":"Discret Math"},{"issue":"1\u20132","key":"897_CR21","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0304-3975(98)00180-7","volume":"225","author":"W Pak-Ken","year":"1999","unstructured":"Pak-Ken W (1999) Optimal path cover problem on block graphs. Theore Comput Sci 225(1\u20132):163\u2013169","journal-title":"Theore Comput Sci"},{"key":"897_CR22","doi-asserted-by":"crossref","unstructured":"Prieto E, Sloper C (2003) Either\/or: Using vertex cover structure in designing fpt-algorithms\u2014the case of k-internal spanning tree. In: Workshop on algorithms and data structures, Springer, pp 474\u2013483","DOI":"10.1007\/978-3-540-45078-8_41"},{"issue":"50","key":"897_CR23","doi-asserted-by":"publisher","first-page":"5273","DOI":"10.1016\/j.tcs.2009.08.029","volume":"410","author":"G Salamon","year":"2009","unstructured":"Salamon G (2009) Approximating the maximum internal spanning tree problem. Theor Comput Sci 410(50):5273\u20135284","journal-title":"Theor Comput Sci"},{"key":"897_CR24","unstructured":"Salamon G (2010) Degree-based spanning tree optimization. PhD Thesis"},{"issue":"5","key":"897_CR25","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.ipl.2007.08.030","volume":"105","author":"G Salamon","year":"2008","unstructured":"Salamon G, Wiener G (2008) On finding spanning trees with few leaves. Inf Process Lett 105(5):164\u2013169","journal-title":"Inf Process Lett"},{"issue":"2","key":"897_CR26","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0095-8956(74)90063-X","volume":"16","author":"D Seinsche","year":"1974","unstructured":"Seinsche D (1974) On a property of the class of n-colorable graphs. J Comb Theory Series B 16(2):191\u2013193","journal-title":"J Comb Theory Series B"},{"issue":"3","key":"897_CR27","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 (1987) Bipartite permutation graphs. Discret Appl Math 18(3):279\u2013292","journal-title":"Discret Appl Math"},{"issue":"2","key":"897_CR28","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/0304-3975(93)90123-B","volume":"115","author":"R Srikant","year":"1993","unstructured":"Srikant R, Sundaram R, Singh KS et al (1993) Optimal path cover problem on block graphs and bipartite permutation graphs. Theor Comput Sci 115(2):351\u2013357","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00897-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00897-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00897-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T09:39:53Z","timestamp":1667036393000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00897-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,5]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["897"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00897-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,5]]},"assertion":[{"value":"13 August 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 September 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}