{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T01:08:46Z","timestamp":1725757726950},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319037790"},{"type":"electronic","value":"9783319037806"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03780-6_24","type":"book-chapter","created":{"date-parts":[[2013,11,21]],"date-time":"2013-11-21T01:13:18Z","timestamp":1384996398000},"page":"272-283","source":"Crossref","is-referenced-by-count":4,"title":["Circular Convex Bipartite Graphs: Feedback Vertex Set"],"prefix":"10.1007","author":[{"given":"Zhao","family":"Lu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Min","family":"Lu","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":"#cr-split#-24_CR1.1","doi-asserted-by":"crossref","unstructured":"Bao, F.S., Zhang, Y.: A review of tree convex sets test. Computational Intelligence\u00a028(3), 358-372 (2012)","DOI":"10.1111\/j.1467-8640.2012.00418.x"},{"key":"#cr-split#-24_CR1.2","unstructured":"Previous version: A survey of tree convex sets test. arXiv.0906.0205 (2009)"},{"key":"24_CR2","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1613\/jair.638","volume":"12","author":"A. Becker","year":"2000","unstructured":"Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized Algorithms for the Loop Cutset Problem. J. Artif. Intell. Res.\u00a012, 219\u2013234 (2000)","journal-title":"J. Artif. Intell. Res."},{"key":"24_CR3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes - A Survey","author":"A. Brandstad","year":"1999","unstructured":"Brandstad, A., Le, V.B., Spinrad, J.P.: Graph Classes - A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"key":"24_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-13731-0_10","volume-title":"Algorithm Theory - SWAT 2010","author":"Y. Cao","year":"2010","unstructured":"Cao, Y., Chen, J., Liu, Y.: On Feedback Vertex Set: New Measure and New Structures. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 93\u2013104. Springer, Heidelberg (2010)"},{"key":"24_CR5","first-page":"27","volume":"98","author":"M. Dom","year":"2009","unstructured":"Dom, M.: Algorithmic aspects of the consecutive ones property. Bulletin of the EATCS\u00a098, 27\u201359 (2009)","journal-title":"Bulletin of the EATCS"},{"key":"24_CR6","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."},{"issue":"2","key":"24_CR7","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00453-007-9152-0","volume":"52","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Gaspers, S., Pyatkin, A., Razgon, I.: On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms. Algorithmica\u00a052(2), 293\u2013307 (2008)","journal-title":"Algorithmica"},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Handbook of Combinatorial Optimization, (suppl. vol.\u00a0A), pp. 209\u2013258. Kluwer Academic Publishers (1999)","DOI":"10.1007\/978-1-4757-3023-4_4"},{"key":"24_CR9","unstructured":"Fomin, F.V., Villanger, Y.: Finding Induced Subgraphs via Minimal Triangulations. In: Proc. of STACS, pp. 383\u2013394 (2010)"},{"key":"24_CR10","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":"24_CR11","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"24_CR12","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":"24_CR13","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":"24_CR14","doi-asserted-by":"crossref","unstructured":"Guo, J.: Undirected feedback vertex set. Encyclopedia of Algorithms, 995\u2013996 (2008)","DOI":"10.1007\/978-0-387-30162-4_450"},{"key":"24_CR15","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":"24_CR16","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":"24_CR17","doi-asserted-by":"crossref","unstructured":"Jiang, W., Liu, T., Wang, C., Xu, K.: Feedback vertex sets on restricted bipartite graphs. Theor. Comput. Sci. (in press, 2013), doi: 10.1016\/j.tcs.2012.12.021","DOI":"10.1016\/j.tcs.2012.12.021"},{"key":"24_CR18","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":"24_CR19","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":"24_CR20","unstructured":"Kloks, T., Liu, C.H., Pon, S.H.: Feedback vertex set on chordal bipartite graphs. arXiv:1104.3915 (2011)"},{"key":"24_CR21","unstructured":"Kloks, T., Wang, Y.L.: Advances in graph algorithms. Manuscipt of a book (2013)"},{"key":"24_CR22","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":"24_CR23","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":"24_CR24","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":"24_CR25","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)"},{"key":"24_CR26","doi-asserted-by":"publisher","first-page":"4144","DOI":"10.1016\/j.disc.2007.08.007","volume":"308","author":"F.R. Madelaine","year":"2008","unstructured":"Madelaine, F.R., Stewart, I.A.: Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies. Discrete Math.\u00a0308, 4144\u20134164 (2008)","journal-title":"Discrete Math."},{"key":"24_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":"24_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)"},{"issue":"4","key":"24_CR29","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/j.ipl.2003.11.001","volume":"89","author":"F.H. Wang","year":"2004","unstructured":"Wang, F.H., Wang, Y.L., Chang, J.M.: Feedback vertex sets in star graphs. Inform. Process. Lett.\u00a089(4), 203\u2013208 (2004)","journal-title":"Inform. Process. Lett."},{"key":"24_CR30","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."},{"key":"24_CR31","unstructured":"Zhou, H.: The feedback vertex set problem: a spin glass approach. arXiv:1307.6948 (2013)"},{"key":"24_CR32","unstructured":"Van Zuylen, A.: Linear programming based approximation algorithms for feedback set problems in bipartite tournaments. Theor. Comput. Sci. (in press)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03780-6_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T09:39:13Z","timestamp":1558690753000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03780-6_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319037790","9783319037806"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03780-6_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}