{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,17]],"date-time":"2026-05-17T05:09:49Z","timestamp":1778994589943,"version":"3.51.4"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,6,10]],"date-time":"2015-06-10T00:00:00Z","timestamp":1433894400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61370052"],"award-info":[{"award-number":["61370052"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61370156"],"award-info":[{"award-number":["61370156"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s10878-015-9917-3","type":"journal-article","created":{"date-parts":[[2015,6,10]],"date-time":"2015-06-10T16:14:58Z","timestamp":1433952898000},"page":"95-110","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs"],"prefix":"10.1007","volume":"32","author":[{"given":"Hao","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zihan","family":"Lei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tian","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziyang","family":"Tang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chaoyi","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,10]]},"reference":[{"key":"9917_CR1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg S, Corneil DG, Proskurowski A (1987) Complexity of finding embeddings in a k-tree. SIAM J Algebr Discret Methods 8:277\u2013284","journal-title":"SIAM J Algebr Discret Methods"},{"key":"9917_CR2","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes\u2014a survey","author":"A Brandst\u00e4d","year":"1999","unstructured":"Brandst\u00e4d A, Le VB, Spinrad JP (1999) Graph classes\u2014a survey. Society for Industrial and Applied Mathematics, Philadelphia"},{"key":"9917_CR3","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/s10878-008-9177-6","volume":"19","author":"L Chen","year":"2010","unstructured":"Chen L, Lu C, Zeng Z (2010) Labelling algorithms for paired-domination problems in block and interval graphs. J Comb Optim 19:457\u2013470","journal-title":"J Comb Optim"},{"key":"9917_CR4","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0020-0190(90)90147-P","volume":"36","author":"P Damaschke","year":"1990","unstructured":"Damaschke P, Muller H, Kratsch D (1990) Domination in convex and chordal bipartite graphs. Inform Proc Lett 36:231\u2013236","journal-title":"Inform Proc Lett"},{"key":"9917_CR5","volume-title":"Computers and intractability, a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of NP-completeness. W.H. Freeman and Company, New York"},{"key":"9917_CR6","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1002\/jgt.3190020209","volume":"2","author":"MC Golumbic","year":"1978","unstructured":"Golumbic MC, Goss CF (1978) Perfect elimination and chordal bipartite graphs. J Graph Theory 2:155\u2013163","journal-title":"J Graph Theory"},{"key":"9917_CR7","doi-asserted-by":"crossref","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs, Annals of discrete mathematics, vol 57, 2nd edn. Elsevier B.V., Amsterdam","DOI":"10.1016\/S0167-5060(04)80059-1"},{"key":"9917_CR8","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1002\/nav.3800140304","volume":"14","author":"F Grover","year":"1967","unstructured":"Grover F (1967) Maximum matching in a convex bipartite graph. Nav Res Logist Q 14:313\u2013316","journal-title":"Nav Res Logist Q"},{"key":"9917_CR9","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1007\/s00224-011-9378-8","volume":"50","author":"R-W Hung","year":"2012","unstructured":"Hung R-W (2012) Linear-time algorithm for the paired-domination problem in convex bipartite graphs. Theory Comput Syst 50:721\u2013738","journal-title":"Theory Comput Syst"},{"key":"9917_CR10","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0020-0190(91)90188-N","volume":"37","author":"W Irving","year":"1991","unstructured":"Irving W (1991) On approximating the minimum independent dominating set. Inform Process Lett 37:197\u2013200","journal-title":"Inform Process Lett"},{"key":"9917_CR11","doi-asserted-by":"crossref","unstructured":"Jiang W, Liu T, Ren T, Xu K (2011) Two hardness results on feedback vertex sets. Proceedings of FAW-AAIM 2011, pp 233\u2013243","DOI":"10.1007\/978-3-642-21204-8_26"},{"key":"9917_CR12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.tcs.2012.12.021","volume":"507","author":"W Jiang","year":"2013","unstructured":"Jiang W, Liu T, Wang C, Xu K (2013) Feedback vertex sets on restricted bipartite graphs. Theory Comput Sci 507:41\u201351","journal-title":"Theory Comput Sci"},{"key":"9917_CR13","doi-asserted-by":"crossref","unstructured":"Jiang W, Liu T, Xu K (2011) Tractable feedback vertex sets in restricted bipartite graphs. Proceedings of COCOA 2011, pp 424\u2013434","DOI":"10.1007\/978-3-642-22616-8_33"},{"key":"9917_CR14","series-title":"Reducibility among combinatorial problems","volume-title":"Complexity of computer computations","author":"R Karp","year":"1972","unstructured":"Karp R (1972) Complexity of computer computations., Reducibility among combinatorial problemsPlenum Press, New York"},{"key":"9917_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: computations and approximations","author":"T Kloks","year":"1994","unstructured":"Kloks T (1994) Treewidth: computations and approximations. Springer, Berlin"},{"key":"9917_CR16","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1006\/jagm.1995.1037","volume":"19","author":"T Kloks","year":"1995","unstructured":"Kloks T, Kratsch D (1995) Treewidth of chordal bipartite graphs. J Algorithms 19:266\u2013281","journal-title":"J Algorithms"},{"key":"9917_CR17","unstructured":"Kloks T, Liu CH, Pon SH (2011) Feedback vertex set on chordal bipartite graphs. arXiv:1104.3915"},{"key":"9917_CR18","unstructured":"Kloks T,Wang YL (2013) Advances in graph slgorithms. Manuscript"},{"issue":"1","key":"9917_CR19","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/990518.990521","volume":"7","author":"MS Krishnamoorthy","year":"1975","unstructured":"Krishnamoorthy MS (1975) An NP-hard problem in bipartite graphs. SIGACT News 7(1):26","journal-title":"SIGACT News"},{"key":"9917_CR20","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(95)00145-3","volume":"56","author":"YD Liang","year":"1995","unstructured":"Liang YD, Blum N (1995) Circular convex bipartite graphs: maximum matching and Hamiltonian circuits. Inf Process Lett 56:215\u2013219","journal-title":"Inf Process Lett"},{"key":"9917_CR21","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s002360050088","volume":"34","author":"YD Liang","year":"1997","unstructured":"Liang YD, Chang MS (1997) Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Informatica 34:337\u2013346","journal-title":"Acta Informatica"},{"key":"9917_CR22","doi-asserted-by":"crossref","unstructured":"Liu T (2014) Restricted bipartite graphs: comparison and hardness results. Proceddings of AAIM, pp 241\u2013252","DOI":"10.1007\/978-3-319-07956-1_22"},{"key":"9917_CR23","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s10878-014-9729-x","volume":"29","author":"T Liu","year":"2015","unstructured":"Liu T, Lu Z, Xu K (2015) Tractable connected domination for restricted bipartite graphs. J Comb Optim 29:247\u2013256","journal-title":"J Comb Optim"},{"key":"9917_CR24","doi-asserted-by":"crossref","unstructured":"Lu M, Liu T, Xu K (2013) Independent domination: reductions from circular- and triad-convex bipartite graphs to convex bipartite graphs. Proceedings of FAW-AAIM, pp 142\u2013152","DOI":"10.1007\/978-3-642-38756-2_16"},{"key":"9917_CR25","doi-asserted-by":"crossref","unstructured":"Lu M, Liu T, Tong W, Lin G, Xu K (2014) Set cover, set packing and hitting set for tree convex and tree-like set systems. Proceedings of TAMC, pp 248\u2013258","DOI":"10.1007\/978-3-319-06089-7_17"},{"key":"9917_CR26","doi-asserted-by":"crossref","unstructured":"Liu T, Xu K (2015) Union-closed tree convex sets. Proceedings of FAW, to appear","DOI":"10.1007\/978-3-319-19647-3_19"},{"issue":"1\u20133","key":"9917_CR27","doi-asserted-by":"crossref","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. Disc Math 156(1\u20133):291\u2013298","journal-title":"Disc Math"},{"issue":"2\u20133","key":"9917_CR28","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0304-3975(87)90067-3","volume":"53","author":"H M\u00fcller","year":"1987","unstructured":"M\u00fcller H, Brandst\u00e4t A (1987) The NP-completeness of steiner tree and dominating set for chordal bipartite graphs. Theory Comput Sci 53(2\u20133):257\u2013265","journal-title":"Theory Comput Sci"},{"key":"9917_CR29","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1007\/s10878-012-9483-x","volume":"26","author":"BS Panda","year":"2013","unstructured":"Panda BS, Prahan D (2013) Minimum paired-dominating set in chordal graphs and perfect elimination bipartite graphs. J Comb Optim 26:770\u2013785","journal-title":"J Comb Optim"},{"key":"9917_CR30","doi-asserted-by":"crossref","unstructured":"Pandey A, Panda BS (2015) Domination in some subclasses of bipartite graphs. Proceedings of CALDAM 2015, pp 169\u2013180","DOI":"10.1007\/978-3-319-14974-5_17"},{"key":"9917_CR31","unstructured":"Pfaff J, Laskar R, Hedetniemi ST (1983) NP-completeness of total and connected domination, and irredundance for bipartite graphs. Technical Report 428, Department Mathematical Sciences, Clemenson University"},{"key":"9917_CR32","doi-asserted-by":"crossref","unstructured":"Song Y, Liu T, Xu K (2012) Independent domination on tree convex bipartite graphs. Proceedings of FAW-AAIM 2012, pp 129\u2013138","DOI":"10.1007\/978-3-642-29700-7_12"},{"key":"9917_CR33","doi-asserted-by":"crossref","unstructured":"Wang C, Liu T, Jiang W, Xu K (2012) Feedback vertex sets on tree convex bipartite graphs. Proceedings of COCOA 2012, pp 95\u2013102","DOI":"10.1007\/978-3-642-31770-5_9"},{"key":"9917_CR34","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis M (1981) Node-deletion problem on bipartite graphs. SIAM J Comput 10:310\u2013327","journal-title":"SIAM J Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9917-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-015-9917-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9917-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,26]],"date-time":"2019-08-26T09:51:57Z","timestamp":1566813117000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-015-9917-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,10]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["9917"],"URL":"https:\/\/doi.org\/10.1007\/s10878-015-9917-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,10]]}}}