{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:35:31Z","timestamp":1762324531298,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030250263"},{"type":"electronic","value":"9783030250270"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","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":[[2019]]},"DOI":"10.1007\/978-3-030-25027-0_13","type":"book-chapter","created":{"date-parts":[[2019,8,1]],"date-time":"2019-08-01T00:04:09Z","timestamp":1564617849000},"page":"185-200","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Extension of Some Edge Graph Problems: Standard and Parameterized Complexity"],"prefix":"10.1007","author":[{"given":"Katrin","family":"Casel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mehdi","family":"Khosravian Ghadikolaei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00f4me","family":"Monnot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,10]]},"reference":[{"key":"13_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-319-29221-2_6","volume-title":"Algorithms and Discrete Applied Mathematics","author":"C Bazgan","year":"2016","unstructured":"Bazgan, C., Brankovic, L., Casel, K., Fernau, H.: On the complexity landscape of the domination chain. In: Govindarajan, S., Maheshwari, A. (eds.) CALDAM 2016. LNCS, vol. 9602, pp. 61\u201372. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-29221-2_6"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2017.05.042","volume":"717","author":"C Bazgan","year":"2018","unstructured":"Bazgan, C., et al.: The many facets of upper domination. Theor. Comput. Sci. 717, 2\u201325 (2018)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"13_CR3","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1016\/j.tcs.2007.06.009","volume":"385","author":"A Berger","year":"2007","unstructured":"Berger, A., Fukunaga, T., Nagamochi, H., Parekh, O.: Approximability of the capacitated b-edge dominating set problem. Theor. Comput. Sci. 385(1\u20133), 202\u2013213 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"13_CR4","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/s00453-007-9057-y","volume":"50","author":"A Berger","year":"2008","unstructured":"Berger, A., Parekh, O.: Linear time algorithms for generalized edge dominating set problems. Algorithmica 50(2), 244\u2013254 (2008)","journal-title":"Algorithmica"},{"key":"13_CR5","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT. ECCC (049) (2003)"},{"issue":"1","key":"13_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","volume":"19","author":"AA Bertossi","year":"1984","unstructured":"Bertossi, A.A.: Dominating sets for split and bipartite graphs. Inf. Process. Lett. 19(1), 37\u201340 (1984)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"13_CR7","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0012-365X(92)90646-W","volume":"100","author":"M Bir\u00f3","year":"1992","unstructured":"Bir\u00f3, M., Hujter, M., Tuza, Z.: Precoloring extension. I. Interval graphs. Disc. Math. 100(1\u20133), 267\u2013279 (1992)","journal-title":"Disc. Math."},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Bonamy, M., Defrain, O., Heinrich, M., Raymond, J.-F.: Enumerating minimal dominating sets in triangle-free graphs. In: Niedermeier, R., Paul, C. (eds.) STACS, Dagstuhl, Germany. Leibniz International Proceedings in Informatics (LIPIcs), vol. 126, pp. 16:1\u201316:12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)","DOI":"10.1145\/3386686"},{"issue":"2","key":"13_CR9","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1080\/10556789808805708","volume":"10","author":"E Boros","year":"1998","unstructured":"Boros, E., Gurvich, V., Hammer, P.L.: Dual subimplicants of positive Boolean functions. Optim. Meth. Softw. 10(2), 147\u2013156 (1998)","journal-title":"Optim. Meth. Softw."},{"issue":"26\u201328","key":"13_CR10","doi-asserted-by":"publisher","first-page":"2581","DOI":"10.1016\/j.tcs.2010.03.021","volume":"411","author":"J Cardinal","year":"2010","unstructured":"Cardinal, J., Levy, E.: Connected vertex covers in dense graphs. Theor. Comput. Sci. 411(26\u201328), 2581\u20132590 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR11","unstructured":"Casel, K., Fernau, H., Khosravian Ghadikoei, M., Monnot, J., Sikora, F.: On the complexity of solution extension of optimization problems. CoRR, abs\/1810.04553 (2018)"},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-030-17402-6_11","volume-title":"Algorithms and Complexity","author":"K Casel","year":"2019","unstructured":"Casel, K., Fernau, H., Ghadikoalei, M.K., Monnot, J., Sikora, F.: Extension of vertex cover and independent set in some classes of graphs. In: Heggernes, P. (ed.) CIAC 2019. LNCS, vol. 11485, pp. 124\u2013136. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17402-6_11"},{"issue":"1","key":"13_CR13","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0166-218X(84)90075-1","volume":"8","author":"CJ Colbourn","year":"1984","unstructured":"Colbourn, C.J.: The complexity of completing partial Latin squares. Disc. Appl. Math. 8(1), 25\u201330 (1984)","journal-title":"Disc. Appl. Math."},{"key":"13_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-030-17953-3_14","volume-title":"Integer Programming and Combinatorial Optimization","author":"S Dudycz","year":"2019","unstructured":"Dudycz, S., Lewandowski, M., Marcinkowski, J.: Tight approximation ratio for minimum maximal matching. In: Lodi, A., Nagarajan, V. (eds.) IPCO 2019. LNCS, vol. 11480, pp. 181\u2013193. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17953-3_14"},{"issue":"2","key":"13_CR15","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/s00224-014-9549-5","volume":"56","author":"B Escoffier","year":"2015","unstructured":"Escoffier, B., Monnot, J., Paschos, V.T., Xiao, M.: New results on polynomial inapproximabilityand fixed parameter approximability of edge dominating set. Theory Comput. Syst. 56(2), 330\u2013346 (2015)","journal-title":"Theory Comput. Syst."},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/11847250_13","volume-title":"Parameterized and Exact Computation","author":"H Fernau","year":"2006","unstructured":"Fernau, H.: edge dominating set: efficient enumeration-based exact algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 142\u2013153. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11847250_13"},{"key":"13_CR17","unstructured":"Fernau, H., Hoffmann, S.: Extensions to minimal synchronizing words. J. Autom. Lang. Comb. 24 (2019)"},{"key":"13_CR18","unstructured":"Fernau, H., Manlove, D.F., Monnot, J.: Algorithmic study of upper edge dominating set (2019, manuscript)"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Johnson, D.S., et al. (eds.) STOC, pp. 448\u2013456. ACM (1983)","DOI":"10.1145\/800061.808776"},{"key":"13_CR20","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. (1979)"},{"issue":"3","key":"13_CR21","doi-asserted-by":"publisher","first-page":"836","DOI":"10.1007\/s00453-014-9875-7","volume":"72","author":"PA Golovach","year":"2015","unstructured":"Golovach, P.A., Heggernes, P., Kratsch, D., Vilnger, Y.: An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Algorithmica 72(3), 836\u2013859 (2015)","journal-title":"Algorithmica"},{"key":"13_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-642-35261-4_32","volume-title":"Algorithms and Computation","author":"MM Kant\u00e9","year":"2012","unstructured":"Kant\u00e9, M.M., Limouzy, V., Mary, A., Nourine, L.: On the neighbourhood helly of some graph classes and applications to the enumeration of minimal dominating sets. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 289\u2013298. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-35261-4_32"},{"key":"13_CR23","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(94)90143-0","volume":"52","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math. 52, 233\u2013252 (1994)","journal-title":"Discrete Appl. Math."},{"key":"13_CR24","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1137\/0209042","volume":"9","author":"EL Lawler","year":"1980","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM J. Comput. 9, 558\u2013565 (1980)","journal-title":"SIAM J. Comput."},{"key":"13_CR25","unstructured":"McRae, A.A.: Generalizing NP-completeness proofs for bipartite and chordal graphs. Ph.D. thesis, Clemson University, Department of Computer Science, South Carolina (1994)"},{"issue":"4","key":"13_CR26","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s00453-011-9546-x","volume":"64","author":"JMM van Rooij","year":"2012","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Exact algorithms for edge domination. Algorithmica 64(4), 535\u2013563 (2012)","journal-title":"Algorithmica"},{"key":"13_CR27","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)"},{"key":"13_CR28","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Vitter, J.S., Spirakis, P.G., Yannakakis, M. (eds.) STOC, pp. 453\u2013461. ACM (2001)","DOI":"10.1145\/380752.380839"},{"key":"13_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/3-540-63890-3_11","volume-title":"Algorithms and Computation","author":"T Uno","year":"1997","unstructured":"Uno, T.: Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. In: Leong, H.W., Imai, H., Jain, S. (eds.) ISAAC 1997. LNCS, vol. 1350, pp. 92\u2013101. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63890-3_11"},{"key":"13_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-642-02270-8_25","volume-title":"Frontiers in Algorithmics","author":"J Wang","year":"2009","unstructured":"Wang, J., Chen, B., Feng, Q., Chen, J.: An efficient fixed-parameter enumeration algorithm for weighted edge dominating set. In: Deng, X., Hopcroft, J.E., Xue, J. (eds.) FAW 2009. LNCS, vol. 5598, pp. 237\u2013250. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02270-8_25"},{"issue":"3","key":"13_CR31","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"13_CR32","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-25027-0_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T13:24:56Z","timestamp":1710336296000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-25027-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030250263","9783030250270"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-25027-0_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"10 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Copenhagen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Denmark","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct0","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/di.ku.dk\/fct2019","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}