{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:56Z","timestamp":1759638956290,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662557501"},{"type":"electronic","value":"9783662557518"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-662-55751-8_30","type":"book-chapter","created":{"date-parts":[[2017,8,15]],"date-time":"2017-08-15T11:32:49Z","timestamp":1502796769000},"page":"381-394","source":"Crossref","is-referenced-by-count":2,"title":["Polynomial-Time Algorithms for the Subset Feedback Vertex Set Problem on Interval Graphs and Permutation Graphs"],"prefix":"10.1007","author":[{"given":"Charis","family":"Papadopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Spyridon","family":"Tzimas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,16]]},"reference":[{"issue":"4","key":"30_CR1","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1137\/S0097539796305109","volume":"27","author":"R Bar-Yehuda","year":"1998","unstructured":"Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and bayesian inference. SIAM J. Comput. 27(4), 942\u2013959 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"30_CR2","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0004-3702(95)00004-6","volume":"83","author":"A Becker","year":"1996","unstructured":"Becker, A., Geiger, D.: Optimization of Pearl\u2019s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell. 83(1), 167\u2013188 (1996)","journal-title":"Artif. Intell."},{"key":"30_CR3","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.tcs.2013.01.011","volume":"511","author":"R Belmonte","year":"2013","unstructured":"Belmonte, R., Vatshelle, M.: Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci. 511, 54\u201365 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"30_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-56402-0_30","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A Brandst\u00e4dt","year":"1993","unstructured":"Brandst\u00e4dt, A.: On improved time bounds for permutation graph problems. In: Mayr, E.W. (ed.) WG 1992. LNCS, vol. 657, pp. 1\u201310. Springer, Heidelberg (1993). doi:\n10.1007\/3-540-56402-0_30"},{"key":"30_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BFb0028791","volume-title":"Fundamentals of Computation Theory","author":"A Brandst\u00e4dt","year":"1985","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On the restriction of some NP-complete graph problems to permutation graphs. In: Budach, L. (ed.) FCT 1985. LNCS, vol. 199, pp. 53\u201362. Springer, Heidelberg (1985). doi:\n10.1007\/BFb0028791"},{"issue":"2","key":"30_CR6","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(87)90128-9","volume":"54","author":"A Brandst\u00e4dt","year":"1987","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On domination problems for permutation and other graphs. Theor. Comput. Sci. 54(2), 181\u2013198 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"30_CR7","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999). \nhttp:\/\/dx.doi.org\/10.1137\/1.9780898719796"},{"issue":"3","key":"30_CR8","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1016\/j.ejc.2012.07.023","volume":"34","author":"B-M Bui-Xuan","year":"2013","unstructured":"Bui-Xuan, B.-M., Such\u00fd, O., Telle, J.A., Vatshelle, M.: Feedback vertex set on graphs of low clique-width. Eur. J. Comb. 34(3), 666\u2013679 (2013)","journal-title":"Eur. J. Comb."},{"key":"30_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30162-4_253","volume-title":"Encyclopedia of Algorithms","author":"G Calinescu","year":"2008","unstructured":"Calinescu, G.: Multiway cut. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms. Springer, New York (2008). doi:\n10.1007\/978-0-387-30162-4_253"},{"key":"30_CR10","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.jcss.2017.04.003","volume":"88","author":"RH Chitnis","year":"2017","unstructured":"Chitnis, R.H., Fomin, F.V., Lokshtanov, D., Misra, P., Ramanujan, M.S., Saurabh, S.: Faster exact algorithms for some terminal set problems. J. Comput. Syst. Sci. 88, 195\u2013207 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"30_CR11","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0166-218X(88)90086-8","volume":"22","author":"DG Corneil","year":"1988","unstructured":"Corneil, D.G., Fonlupt, J.: The complexity of generalized clique covering. Discret. Appl. Math. 22(2), 109\u2013118 (1988)","journal-title":"Discret. Appl. Math."},{"key":"30_CR12","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33, 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"30_CR13","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1137\/110843071","volume":"27","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discret. Math. 27(1), 290\u2013309 (2013)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"30_CR14","doi-asserted-by":"crossref","first-page":"1231","DOI":"10.1137\/S0097539798340047","volume":"30","author":"G Even","year":"2000","unstructured":"Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput. 30(4), 1231\u20131252 (2000)","journal-title":"SIAM J. Comput."},{"key":"30_CR15","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1007\/978-0-387-74759-0_178","volume-title":"Encyclopedia of Optimization","author":"P Festa","year":"2009","unstructured":"Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 1005\u20131016. Springer, New York (2009). doi:\n10.1007\/978-0-387-74759-0_178"},{"key":"30_CR16","first-page":"764","volume":"2016","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Gaspers, S., Lokshtanov, D., Saurabh, S.: Exact algorithms via monotone local search. Proc. STOC 2016, 764\u2013775 (2016)","journal-title":"Proc. STOC"},{"issue":"1","key":"30_CR17","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/s00453-012-9731-6","volume":"69","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Heggernes, P., Kratsch, D., Papadopoulos, C., Villanger, Y.: Enumerating minimal subset feedback vertex sets. Algorithmica 69(1), 216\u2013231 (2014)","journal-title":"Algorithmica"},{"key":"30_CR18","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15, 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"key":"30_CR19","volume-title":"Computers and Intractability","author":"MR Garey","year":"1978","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Co., San Francisco (1978)"},{"issue":"1","key":"30_CR20","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0196-6774(03)00111-1","volume":"50","author":"N Garg","year":"2004","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs. J. Algorithms 50(1), 49\u201361 (2004)","journal-title":"J. Algorithms"},{"key":"30_CR21","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/j.jda.2013.09.005","volume":"26","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Heggernes, P., Kratsch, D., Saei, R.: Subset feedback vertex sets in chordal graphs. J. Discret. Algorithms 26, 7\u201315 (2014)","journal-title":"J. Discret. Algorithms"},{"key":"30_CR22","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. Elsevier, Amsterdam (2004)"},{"issue":"3","key":"30_CR23","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423\u2013443 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"30_CR24","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1016\/j.ejor.2007.02.014","volume":"186","author":"J Guo","year":"2008","unstructured":"Guo, J., Huffner, F., Kenar, E., Niedermeier, R., Uhlmann, J.: Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs. Eur. J. Oper. Res. 186, 542\u2013553 (2008)","journal-title":"Eur. J. Oper. Res."},{"issue":"10","key":"30_CR25","doi-asserted-by":"crossref","first-page":"1936","DOI":"10.1016\/j.dam.2007.10.006","volume":"156","author":"D Kratsch","year":"2008","unstructured":"Kratsch, D., M\u00fcller, H., Todinca, I.: Feedback vertex set on AT-free graphs. Discret. Appl. Math. 156(10), 1936\u20131947 (2008)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"30_CR26","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0020-0190(94)00133-2","volume":"52","author":"YD Liang","year":"1994","unstructured":"Liang, Y.D.: On the feedback vertex set problem in permutation graphs. Inf. Process. Lett. 52(3), 123\u2013129 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"30_CR27","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s002360050088","volume":"34","author":"YD Liang","year":"1997","unstructured":"Liang, Y.D., Chang, M.-S.: Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Inform. 34(5), 337\u2013346 (1997)","journal-title":"Acta Inform."},{"issue":"2","key":"30_CR28","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0020-0190(96)00193-7","volume":"61","author":"CL Lu","year":"1997","unstructured":"Lu, C.L., Tang, C.Y.: A linear-time algorithm for the weighted feedback vertex problem on interval graphs. Inf. Process. Lett. 61(2), 107\u2013111 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"30_CR29","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0166-218X(97)80001-7","volume":"80","author":"C Maw-Shang","year":"1997","unstructured":"Maw-Shang, C.: Weighted domination of cocomparability graphs. Discret. Appl. Math. 80(2), 135\u2013148 (1997)","journal-title":"Discret. Appl. Math."},{"key":"30_CR30","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discret. Math. 201, 189\u2013241 (1999)","journal-title":"Discret. Math."},{"issue":"12","key":"30_CR31","doi-asserted-by":"crossref","first-page":"1791","DOI":"10.1016\/j.dam.2012.03.021","volume":"160","author":"C Papadopoulos","year":"2012","unstructured":"Papadopoulos, C.: Restricted vertex multicut on permutation graphs. Discret. Appl. Math. 160(12), 1791\u20131797 (2012)","journal-title":"Discret. Appl. Math."},{"key":"30_CR32","series-title":"Fields Institute Monograph Series","volume-title":"Efficient Graph Representations","author":"JP Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. Fields Institute Monograph Series, vol. 19. American Mathematical Society, Providence (2003)"},{"issue":"2","key":"30_CR33","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Node-deletion problems on bipartite graphs. SIAM J. Comput. 10(2), 310\u2013327 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-55751-8_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,8,15]],"date-time":"2017-08-15T11:41:17Z","timestamp":1502797277000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-55751-8_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783662557501","9783662557518"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-55751-8_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}