{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:32:14Z","timestamp":1725795134454},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319080154"},{"type":"electronic","value":"9783319080161"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08016-1_23","type":"book-chapter","created":{"date-parts":[[2014,5,30]],"date-time":"2014-05-30T04:18:07Z","timestamp":1401423487000},"page":"252-263","source":"Crossref","is-referenced-by-count":5,"title":["Tree Convex Bipartite Graphs: $\\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth"],"prefix":"10.1007","author":[{"given":"Chaoyi","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hao","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zihan","family":"Lei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziyang","family":"Tang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tian","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods\u00a08, 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/s10878-008-9177-6","volume":"19","author":"L. Chen","year":"2010","unstructured":"Chen, L., Lu, C., Zeng, Z.: Labelling algorithms for paired-domination problems in block and interval graphs. J. Comb. Optim.\u00a019, 457\u2013470 (2010)","journal-title":"J. Comb. Optim."},{"key":"23_CR3","doi-asserted-by":"publisher","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.: Domination in Convex and Chordal Bipartite Graphs. Inform. Proc. Lett.\u00a036, 231\u2013236 (1990)","journal-title":"Inform. Proc. Lett."},{"key":"23_CR4","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company (1979)"},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1002\/jgt.3190020209","volume":"2","author":"M.C. Golumbic","year":"1978","unstructured":"Golumbic, M.C., Goss, C.F.: Perfect elimination and chordal bipartite graphs. J. Graph Theory\u00a02, 155\u2013163 (1978)","journal-title":"J. Graph Theory"},{"key":"23_CR6","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/nav.3800140304","volume":"14","author":"F. Grover","year":"1967","unstructured":"Grover, F.: Maximum matching in a convex bipartite graph. Nav. Res. Logist. Q.\u00a014, 313\u2013316 (1967)","journal-title":"Nav. Res. Logist. Q."},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1007\/s00224-011-9378-8","volume":"50","author":"R.-W. Hung","year":"2012","unstructured":"Hung, R.-W.: Linear-time algorithm for the paired-domination problem in convex bipartite graphs. Theory Comput. Syst.\u00a050, 721\u2013738 (2012)","journal-title":"Theory Comput. Syst."},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0020-0190(91)90188-N","volume":"37","author":"W. Irving","year":"1991","unstructured":"Irving, W.: On approximating the minimum independent dominating set. Inform. Process. Lett.\u00a037, 197\u2013200 (1991)","journal-title":"Inform. Process. Lett."},{"key":"23_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/978-3-642-21204-8_26","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"W. Jiang","year":"2011","unstructured":"Jiang, W., Liu, T., Ren, T., Xu, K.: Two hardness results on feedback vertex sets. In: Atallah, M., Li, X.-Y., Zhu, B. (eds.) FAW-AAIM 2011. LNCS, vol.\u00a06681, pp. 233\u2013243. Springer, Heidelberg (2011)"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"Jiang, W., Liu, T., Wang, C., Xu, K.: Feedback vertex sets on restricted bipartite graphs. Theor. Comput. Sci. (2013) (in press), doi: 10.1016\/j.tcs.2012.12.021","DOI":"10.1016\/j.tcs.2012.12.021"},{"key":"23_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/978-3-642-22616-8_33","volume-title":"Combinatorial Optimization and Applications","author":"W. Jiang","year":"2011","unstructured":"Jiang, W., Liu, T., Xu, K.: Tractable feedback vertex sets in restricted bipartite graphs. In: Wang, W., Zhu, X., Du, D.-Z. (eds.) COCOA 2011. LNCS, vol.\u00a06831, pp. 424\u2013434. Springer, Heidelberg (2011)"},{"key":"23_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. Karp","year":"1972","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth: Computations and Approximations. Springer (1994)","DOI":"10.1007\/BFb0045375"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1006\/jagm.1995.1037","volume":"19","author":"T. Kloks","year":"1995","unstructured":"Kloks, T., Kratsch, D.: Treewidth of chordal bipartite graphs. J. Algorithms\u00a019, 266\u2013281 (1995)","journal-title":"J. Algorithms"},{"key":"23_CR15","unstructured":"Kloks, T., Liu, C.H., Pon, S.H.: Feedback vertex set on chordal bipartite graphs. arXiv:1104.3915 (2011)"},{"key":"23_CR16","unstructured":"Kloks, T., Wang, Y.L.: Advances in Graph Algorithms (2013) (manuscript)"},{"issue":"1","key":"23_CR17","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/990518.990521","volume":"7","author":"M.S. Krishnamoorthy","year":"1975","unstructured":"Krishnamoorthy, M.S.: An NP-hard problem in bipartite graphs. SIGACT News\u00a07(1), 26 (1975)","journal-title":"SIGACT News"},{"key":"23_CR18","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(95)00145-3","volume":"56","author":"Y.D. Liang","year":"1995","unstructured":"Liang, Y.D., Blum, N.: Circular convex bipartite graphs: maximum matching and Hamiltonian circuits. Inf. Process. Lett.\u00a056, 215\u2013219 (1995)","journal-title":"Inf. Process. Lett."},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s002360050088","volume":"34","author":"Y.D. Liang","year":"1997","unstructured":"Liang, Y.D., Chang, M.S.: Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Informatica\u00a034, 337\u2013346 (1997)","journal-title":"Acta Informatica"},{"key":"23_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-642-38756-2_16","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"M. Lu","year":"2013","unstructured":"Lu, M., Liu, T., Xu, K.: Independent domination: Reductions from circular- and triad-convex bipartite graphs to convex bipartite graphs. In: Fellows, M., Tan, X., Zhu, B. (eds.) FAW-AAIM 2013. LNCS, vol.\u00a07924, pp. 142\u2013152. Springer, Heidelberg (2013)"},{"key":"23_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/978-3-319-06089-7_17","volume-title":"Theory and Applications of Models of Computation","author":"M. Lu","year":"2014","unstructured":"Lu, M., Liu, T., Tong, W., Lin, G., Xu, K.: Set cover, set packing and hitting set for tree convex and tree-like set systems. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) TAMC 2014. LNCS, vol.\u00a08402, pp. 248\u2013258. Springer, Heidelberg (2014)"},{"key":"23_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1007\/978-3-642-38768-5_65","volume-title":"Computing and Combinatorics","author":"Z. Lu","year":"2013","unstructured":"Lu, Z., Liu, T., Xu, K.: Tractable connected domination for restricted bipartite graphs (Extended abstract). In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol.\u00a07936, pp. 721\u2013728. Springer, Heidelberg (2013)"},{"issue":"1-3","key":"23_CR23","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.: Hamiltonian circuits in chordal bipartite graphs. Disc. Math.\u00a0156(1-3), 291\u2013298 (1996)","journal-title":"Disc. Math."},{"issue":"2-3","key":"23_CR24","doi-asserted-by":"publisher","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.: The NP-completeness of steiner tree and dominating set for chordal bipartite graphs. Theor. Comput. Sci.\u00a053(2-3), 257\u2013265 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"Panda, B.S., Prahan, D.: Minimum paired-dominating set in chordal graphs and perfect elimination bipartite graphs. J. Comb. Optim. (2012) (in press), doi:10.1007\/s10878-012-9483-x","DOI":"10.1007\/s10878-012-9483-x"},{"key":"23_CR26","unstructured":"Pfaff, J., Laskar, R., Hedetniemi, S.T.: NP-completeness of total and connected domination, and irredundance for bipartite graphs. Technical Report 428, Dept. Mathematical Sciences, Clemenson Univ. (1983)"},{"key":"23_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-642-29700-7_12","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"Y. Song","year":"2012","unstructured":"Song, Y., Liu, T., Xu, K.: Independent domination on tree convex bipartite graphs. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM 2012 and FAW 2012. LNCS, vol.\u00a07285, pp. 129\u2013138. Springer, Heidelberg (2012)"},{"key":"23_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-642-31770-5_9","volume-title":"Combinatorial Optimization and Applications","author":"C. Wang","year":"2012","unstructured":"Wang, C., Liu, T., Jiang, W., Xu, K.: Feedback vertex sets on tree convex bipartite graphs. In: Lin, G. (ed.) COCOA 2012. LNCS, vol.\u00a07402, pp. 95\u2013102. Springer, Heidelberg (2012)"},{"key":"23_CR29","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Node-deletion problem on bipartite graphs. SIAM J. Comput.\u00a010, 310\u2013327 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08016-1_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,31]],"date-time":"2019-01-31T03:02:27Z","timestamp":1548903747000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08016-1_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319080154","9783319080161"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08016-1_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}