{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T05:32:39Z","timestamp":1771651959393,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2017,8,3]],"date-time":"2017-08-03T00:00:00Z","timestamp":1501718400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s00453-017-0349-6","type":"journal-article","created":{"date-parts":[[2017,8,3]],"date-time":"2017-08-03T17:35:33Z","timestamp":1501781733000},"page":"2637-2655","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Dynamic Parameterized Problems"],"prefix":"10.1007","volume":"80","author":[{"given":"R.","family":"Krithika","sequence":"first","affiliation":[]},{"given":"Abhishek","family":"Sahu","sequence":"additional","affiliation":[]},{"given":"Prafullkumar","family":"Tale","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,3]]},"reference":[{"key":"349_CR1","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Cai, S., Egan, J., Shaw, P., Wang. K.: Turbo-charging cominating set with an FPT subroutine: Further Improvements and Experimental Analysis. In: Proceedings of the 14th International Conference on Theory and Applications of Models of Computation pp. 59\u201370. Springer (2017)","DOI":"10.1007\/978-3-319-55911-7_5"},{"issue":"3","key":"349_CR2","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1016\/j.tcs.2015.06.053","volume":"607","author":"FN Abu-Khzam","year":"2015","unstructured":"Abu-Khzam, F.N., Egan, J., Fellows, M.R., Rosamond, F.A.: Shaw. P.: on the parameterized complexity of dynamic problems. Theor. Comput. Sci. 607(3), 426\u2013434 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"349_CR3","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"key":"349_CR4","unstructured":"Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: Proceedings of the $$10th$$ 10 t h Annual ACM-SIAM Symposium on Discrete Algorithms SODA \u201999, pp. 856\u2013857. SIAM (1999)"},{"key":"349_CR5","doi-asserted-by":"crossref","unstructured":"Bonsma, P., Lokshtanov, D.: Feedback vertex set in mixed graphs. In: Proceedings of the 12th International Conference on Algorithms and Data Structures WADS \u201911, pp. 122\u2013133. Springer (2011)","DOI":"10.1007\/978-3-642-22300-6_11"},{"key":"349_CR6","unstructured":"Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and bayesian inference. In: Proceedings of the 5th Annual ACM\u2013SIAM Symposium on Discrete Algorithms SODA \u201994, pp. 344\u2013354. SIAM (1994)"},{"issue":"4","key":"349_CR7","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"349_CR8","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/2925416","volume":"12","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstrom, M.: On problems as hard as CNF-SAT. ACM Trans. Algorithms 12(3), 41 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"349_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., \u0141ukasz, K., Lokshtanov, D., Marx, D., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"2","key":"349_CR10","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41(2), 280\u2013301 (2001)","journal-title":"J. Algorithms"},{"issue":"40\u201342","key":"349_CR11","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"349_CR12","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science FOCS \u201911, pp. 150\u2013159. IEEE (2011)","DOI":"10.1109\/FOCS.2011.23"},{"issue":"4","key":"349_CR13","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1109\/TST.2014.6867515","volume":"19","author":"RG Downey","year":"2014","unstructured":"Downey, R.G., Egan, J., Fellows, M.R., Rosamond, F.A.: Shaw. P.: dynamic dominating set and turbo-charging greedy heuristics. Tsinghua. Sci. Technol. 19(4), 329\u2013337 (2014)","journal-title":"Tsinghua. Sci. Technol."},{"key":"349_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, R.G.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"key":"349_CR15","volume-title":"Raph Theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Raph Theory. Springer, Berlin (2005)"},{"key":"349_CR16","doi-asserted-by":"crossref","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009) pp. 378\u2013389. Springer (2009)","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"349_CR17","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"349_CR18","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Gaspers, S., Lokshtanov, D., Saurabh, S.: Exact algorithms via monotone local search. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing STOC \u201916, pp. 764\u2013775. ACM (2016)","DOI":"10.1145\/2897518.2897551"},{"issue":"2","key":"349_CR19","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181\u2013207 (2009)","journal-title":"Algorithmica"},{"key":"349_CR20","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (exponential) algorithms for the dominating set problem. In: Proceedings of the 30th Workshop on Graph Theoretic Concepts in Computer Science (WG) pp. 245\u2013256. Springer (2005)","DOI":"10.1007\/978-3-540-30559-0_21"},{"key":"349_CR21","unstructured":"Gaspers, S., Gudmundsson, J.,\u00a0Jones, M.,\u00a0Mestre, J., R\u00fcmmele, S.: Turbocharging treewidth heuristics. In: Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) volume\u00a063 of Leibniz International Proceedings in Informatics (LIPIcs) pp. 13:1\u201313:13. Schloss Dagstuhl\u2013Leibniz\u2013Zentrum fuer Informatik (2017)"},{"key":"349_CR22","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.tcs.2012.12.049","volume":"494","author":"S Hartung","year":"2013","unstructured":"Hartung, S., Niedermeier, R.: Incremental list coloring of graphs, parameterized by conservation. Theor. Comput. Sci. 494, 86\u201398 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"10","key":"349_CR23","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1016\/j.ipl.2014.05.001","volume":"114","author":"T Kociumaka","year":"2014","unstructured":"Kociumaka, T., Pilipczuk, M.: Faster deterministic feedback vertex set. Inf. Process. Lett. 114(10), 556\u2013560 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"349_CR24","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci. 289(2), 997\u20131008 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"349_CR25","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"349_CR26","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s10878-011-9394-2","volume":"24","author":"N Misra","year":"2012","unstructured":"Misra, N., Philip, G., Raman, V., Saurabh, S., Sikdar, S.: FPT algorithms for connected feedback vertex set. J. Comb. Optim. 24(2), 131\u2013146 (2012)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"349_CR27","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1145\/1721837.1721848","volume":"6","author":"S Thomass\u00e9","year":"2010","unstructured":"Thomass\u00e9, S.: A $$4k^2$$ 4 k 2 kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32 (2010)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0349-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0349-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0349-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,2]],"date-time":"2019-10-02T00:37:25Z","timestamp":1569976645000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0349-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,3]]},"references-count":27,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["349"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0349-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,3]]}}}