{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T16:21:55Z","timestamp":1784046115781,"version":"3.55.0"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031826696","type":"print"},{"value":"9783031826702","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-82670-2_6","type":"book-chapter","created":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T04:39:36Z","timestamp":1738816776000},"page":"65-79","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized Complexity of\u00a0Generalizations of\u00a0Edge Dominating Set"],"prefix":"10.1007","author":[{"given":"Shubhada","family":"Aute","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Souvik","family":"Saha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anannya","family":"Upasana","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"key":"6_CR1","doi-asserted-by":"publisher","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In: Leighton, F.T., Goodrich, M.T. (eds.) Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23\u201325 May 1994, Montr\u00e9al, Qu\u00e9bec, Canada, pp. 326\u2013335. ACM (1994). https:\/\/doi.org\/10.1145\/195058.195179","DOI":"10.1145\/195058.195179"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-642-32241-9_11","volume-title":"Computing and Combinatorics","author":"R Bevern","year":"2012","unstructured":"Bevern, R.: Towards optimal and expressive kernelization for d-hitting set. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 121\u2013132. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32241-9_11"},{"issue":"2","key":"6_CR3","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009). https:\/\/doi.org\/10.1137\/070683933","journal-title":"SIAM J. Comput."},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/11821069_21","volume-title":"Mathematical Foundations of Computer Science 2006","author":"J Chen","year":"2006","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved parameterized upper bounds for vertex cover. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 238\u2013249. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11821069_21"},{"key":"6_CR5","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"1 &2","key":"6_CR6","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci. 141(1 &2), 109\u2013131 (1995). https:\/\/doi.org\/10.1016\/0304-3975(94)00097-3","journal-title":"Theor. Comput. Sci."},{"key":"6_CR7","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-33293-7_5","volume-title":"Parameterized and Exact Computation","author":"B Escoffier","year":"2012","unstructured":"Escoffier, B., Monnot, J., Paschos, V.T., Xiao, M.: New results on polynomial inapproximability and fixed parameter approximability of edge dominating set. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 25\u201336. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33293-7_5"},{"issue":"4","key":"6_CR9","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998). https:\/\/doi.org\/10.1145\/285055.285059","journal-title":"J. ACM"},{"key":"6_CR10","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"},{"issue":"2","key":"6_CR11","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1007\/s00453-007-9133-3","journal-title":"Algorithmica"},{"key":"6_CR12","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1\u201329:60 (2016). https:\/\/doi.org\/10.1145\/2886094","DOI":"10.1145\/2886094"},{"issue":"3","key":"6_CR13","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0166-218X(00)00383-8","volume":"118","author":"T Fujito","year":"2002","unstructured":"Fujito, T., Nagamochi, H.: A 2-approximation algorithm for the minimum weight edge dominating set problem. Discret. Appl. Math. 118(3), 199\u2013207 (2002). https:\/\/doi.org\/10.1016\/S0166-218X(00)00383-8","journal-title":"Discret. Appl. Math."},{"key":"6_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"6_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/978-3-642-32589-2_44","volume-title":"Mathematical Foundations of Computer Science 2012","author":"T Hagerup","year":"2012","unstructured":"Hagerup, T.: Kernels for edge dominating set: simpler or smaller. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 491\u2013502. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32589-2_44"},{"key":"6_CR16","doi-asserted-by":"publisher","unstructured":"Harris, D.G., Narayanaswamy, N.S.: A faster algorithm for vertex cover parameterized by solution size. CoRR abs\/2205.08022 (2022). https:\/\/doi.org\/10.48550\/arXiv.2205.08022","DOI":"10.48550\/arXiv.2205.08022"},{"key":"6_CR17","doi-asserted-by":"publisher","unstructured":"Harris, D.G., Narayanaswamy, N.S.: A faster algorithm for vertex cover parameterized by solution size. In: Beyersdorff, O., Kant\u00e9, M.M., Kupferman, O., Lokshtanov, D. (eds.) 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, 12\u201314 March 2024, Clermont-Ferrand, France. LIPIcs, vol.\u00a0289, pp. 40:1\u201340:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2024.40","DOI":"10.4230\/LIPIcs.STACS.2024.40"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-319-15612-5_21","volume-title":"WALCOM: Algorithms and Computation","author":"K Iwaide","year":"2015","unstructured":"Iwaide, K., Nagamochi, H.: An improved algorithm for parameterized edge dominating set problem. In: Rahman, M.S., Tomita, E. (eds.) WALCOM 2015. LNCS, vol. 8973, pp. 234\u2013245. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-15612-5_21"},{"key":"6_CR19","doi-asserted-by":"publisher","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. In: Aho, A.V., et al. (eds.) Proceedings of the 5th Annual ACM Symposium on Theory of Computing, 30 April\u20132 May 1973, Austin, Texas, USA, pp. 38\u201349. ACM (1973). https:\/\/doi.org\/10.1145\/800125.804034","DOI":"10.1145\/800125.804034"},{"key":"6_CR20","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a symposium on the Complexity of Computer Computations, held 20\u201322 March 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, pp. 85\u2013103. The IBM Research Symposia Series, Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"23\u201324","key":"6_CR21","doi-asserted-by":"publisher","first-page":"1089","DOI":"10.1016\/j.ipl.2011.09.003","volume":"111","author":"M Lampis","year":"2011","unstructured":"Lampis, M.: A kernel of order 2 k-c log k for vertex cover. Inf. Process. Lett. 111(23\u201324), 1089\u20131091 (2011). https:\/\/doi.org\/10.1016\/j.ipl.2011.09.003","journal-title":"Inf. Process. Lett."},{"key":"6_CR22","unstructured":"Lin, B., Ren, X., Sun, Y., Wang, X.: Constant approximating parameterized k-setcover is w[2]-hard. CoRR abs\/2202.04377 (2022). https:\/\/arxiv.org\/abs\/2202.04377"},{"key":"6_CR23","doi-asserted-by":"publisher","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23\u201325 October 1995, pp. 182\u2013191. IEEE Computer Society (1995). https:\/\/doi.org\/10.1109\/SFCS.1995.492475","DOI":"10.1109\/SFCS.1995.492475"},{"issue":"1","key":"6_CR24","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S1570-8667(03)00009-1","volume":"1","author":"R Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: An efficient fixed-parameter algorithm for 3-hitting set. J. Discret. Algorithms 1(1), 89\u2013102 (2003). https:\/\/doi.org\/10.1016\/S1570-8667(03)00009-1","journal-title":"J. Discret. Algorithms"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Norman, R.Z., Rabin, M.O.: An algorithm for a minimum cover of a graph (1959). https:\/\/api.semanticscholar.org\/CorpusID:120383003","DOI":"10.2307\/2033599"},{"key":"6_CR26","doi-asserted-by":"publisher","unstructured":"Philip, G., Raman, V., Sikdar, S.: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms 9(1), 11:1\u201311:23 (2012). https:\/\/doi.org\/10.1145\/2390176.2390187","DOI":"10.1145\/2390176.2390187"},{"issue":"3","key":"6_CR27","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s00224-007-1334-2","volume":"41","author":"V Raman","year":"2007","unstructured":"Raman, V., Saurabh, S., Sikdar, S.: Efficient exact algorithms through enumerating maximal independent sets and other techniques. Theory Comput. Syst. 41(3), 563\u2013587 (2007). https:\/\/doi.org\/10.1007\/s00224-007-1334-2","journal-title":"Theory Comput. Syst."},{"key":"6_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-540-79723-4_20","volume-title":"Parameterized and Exact Computation","author":"JMM van Rooij","year":"2008","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Exact algorithms for edge domination. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 214\u2013225. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-79723-4_20"},{"issue":"10\u201311","key":"6_CR29","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1016\/j.disc.2011.02.014","volume":"311","author":"A Soleimanfallah","year":"2011","unstructured":"Soleimanfallah, A., Yeo, A.: A kernel of order 2k-c for vertex cover. Discret. Math. 311(10\u201311), 892\u2013895 (2011). https:\/\/doi.org\/10.1016\/j.disc.2011.02.014","journal-title":"Discret. Math."},{"key":"6_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1007\/978-3-642-22993-0_54","volume-title":"Mathematical Foundations of Computer Science 2011","author":"M Xiao","year":"2011","unstructured":"Xiao, M., Kloks, T., Poon, S.-H.: New parameterized algorithms for the edge dominating set problem. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 604\u2013615. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22993-0_54"},{"key":"6_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/978-3-642-29952-0_36","volume-title":"Theory and Applications of Models of Computation","author":"M Xiao","year":"2012","unstructured":"Xiao, M., Nagamochi, H.: A refined exact algorithm for edge dominating set. In: Agrawal, M., Cooper, S.B., Li, A. (eds.) TAMC 2012. LNCS, vol. 7287, pp. 360\u2013372. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29952-0_36"},{"issue":"3","key":"6_CR32","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). https:\/\/doi.org\/10.1137\/0138030","journal-title":"SIAM J. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2025: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-82670-2_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T15:25:26Z","timestamp":1754407526000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-82670-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031826696","9783031826702"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-82670-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"7 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bratislava","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sofsem.sk","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}