{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:15:10Z","timestamp":1761621310123,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319559100"},{"type":"electronic","value":"9783319559117"}],"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":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-55911-7_45","type":"book-chapter","created":{"date-parts":[[2017,3,20]],"date-time":"2017-03-20T10:23:37Z","timestamp":1490005417000},"page":"628-642","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized Complexity of Fair Deletion Problems"],"prefix":"10.1007","author":[{"given":"Tom\u00e1\u0161","family":"Masa\u0159\u00edk","sequence":"first","affiliation":[]},{"given":"Tom\u00e1\u0161","family":"Toufar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,3,21]]},"reference":[{"key":"45_CR1","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0166-218X(83)90101-4","volume":"6","author":"T Ae","year":"1983","unstructured":"Ae, T., Watanabe, T., Nakamura, A.: On the NP-hardness of edge-deletion and -contraction problems. Discrete Appl. Math. 6, 63\u201378 (1983)","journal-title":"Discrete Appl. Math."},{"key":"45_CR2","series-title":"Mathematics in Science and Engineering","volume-title":"Nonserial Dynamic Programming","author":"U Bertel\u00e8","year":"1972","unstructured":"Bertel\u00e8, U., Brioschi, F.: Nonserial Dynamic Programming. Mathematics in Science and Engineering. Academic Press, Orlando (1972)"},{"key":"45_CR3","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. Theor. Comput. Syst. 33, 125\u2013150 (2000)","journal-title":"Theor. Comput. Syst."},{"key":"45_CR4","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci. 109, 49\u201382 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"45_CR5","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1002\/jgt.3190100207","volume":"10","author":"LJ Cowen","year":"1986","unstructured":"Cowen, L.J., Cowen, R., Woodall, D.R.: Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. J. Graph Theor. 10, 187\u2013195 (1986)","journal-title":"J. Graph Theor."},{"key":"45_CR6","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)","edition":"4"},{"key":"45_CR7","series-title":"Texts in Computer Science","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, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)"},{"key":"45_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-642-11269-0_10","volume-title":"Parameterized and Exact Computation","author":"R Enciso","year":"2009","unstructured":"Enciso, R., Fellows, M.R., Guo, J., Kanj, I., Rosamond, F., Such\u00fd, O.: What makes equitable connected partition easy. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 122\u2013133. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-11269-0_10"},{"key":"45_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-540-73556-4_38","volume-title":"Combinatorial Optimization and Applications","author":"M Fellows","year":"2007","unstructured":"Fellows, M., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. In: Dress, A., Xu, Y., Zhu, B. (eds.) COCOA 2007. LNCS, vol. 4616, pp. 366\u2013377. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-73556-4_38"},{"key":"45_CR10","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410, 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"45_CR11","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"45_CR12","unstructured":"Kolman, P., Lidick\u00fd, B., Sereni, J.-S.: Fair edge deletion problems on treedecomposable graphs and improper colorings (2010)"},{"key":"45_CR13","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1137\/0208049","volume":"8","author":"MS Krishnamoorthy","year":"1979","unstructured":"Krishnamoorthy, M.S., Deo, N.: Node-deletion NP-complete problems. SIAM J. Comput. 8, 619\u2013625 (1979)","journal-title":"SIAM J. Comput."},{"key":"45_CR14","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s00453-011-9554-x","volume":"64","author":"M Lampis","year":"2011","unstructured":"Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64, 19\u201337 (2011)","journal-title":"Algorithmica"},{"key":"45_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-10(1:18)2014","volume":"10","author":"M Lampis","year":"2014","unstructured":"Lampis, M.: Model checking lower bounds for simple graphs. Logical Methods Comput. Sci. 10, 1\u201321 (2014)","journal-title":"Logical Methods Comput. Sci."},{"key":"45_CR16","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L Libkin","year":"2004","unstructured":"Libkin, L.: Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2004)"},{"key":"45_CR17","doi-asserted-by":"crossref","first-page":"756","DOI":"10.1109\/12.24280","volume":"38","author":"L Lin","year":"1989","unstructured":"Lin, L., Sahni, S.: Fair edge deletion problems. IEEE Trans. Comput. 38, 756\u2013761 (1989)","journal-title":"IEEE Trans. Comput."},{"key":"45_CR18","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Node- and edge-deletion NP-complete problems. In: ACM STOC, pp. 253\u2013264 (1978)","DOI":"10.1145\/800133.804355"},{"key":"45_CR20","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10, 297\u2013309 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-55911-7_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T20:20:38Z","timestamp":1568924438000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-55911-7_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319559100","9783319559117"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-55911-7_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}