{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:30:14Z","timestamp":1762324214995,"version":"3.40.3"},"publisher-location":"Cham","reference-count":85,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319741796"},{"type":"electronic","value":"9783319741802"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-319-74180-2_1","type":"book-chapter","created":{"date-parts":[[2018,1,15]],"date-time":"2018-01-15T15:12:55Z","timestamp":1516029175000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Domination and Efficient Edge Domination: A Brief Survey"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Brandst\u00e4dt","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,1,16]]},"reference":[{"key":"1_CR1","first-page":"189","volume-title":"Applications of Discrete Mathematics","author":"DW Bange","year":"1988","unstructured":"Bange, D.W., Barkauskas, A.E., Slater, P.J.: Efficient dominating sets in graphs. In: Ringeisen, R.D., Roberts, F.S. (eds.) Applications of Discrete Mathematics, pp. 189\u2013199. SIAM, Philadelphia (1988)"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0012-365X(95)00094-D","volume":"159","author":"DW Bange","year":"1996","unstructured":"Bange, D.W., Barkauskas, A.E., Host, L.H., Slater, P.J.: Generalized domination and efficient domination in graphs. Discrete Math. 159, 1\u201311 (1996)","journal-title":"Discrete Math."},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0095-8956(73)90042-7","volume":"15","author":"N Biggs","year":"1973","unstructured":"Biggs, N.: Perfect codes in graphs. J. Comb. Theory Ser. B 15, 289\u2013296 (1973)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A.: Weighted efficient domination for $$P_5$$-free graphs in linear time. CoRR arXiv:1507.06765v1 (2015)","DOI":"10.1007\/978-3-662-53536-3_4"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0166-218X(97)00125-X","volume":"82","author":"A Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Chepoi, V.D., Dragan, F.F.: The algorithmic use of hypertree structure and maximum neighbourhood orderings. Discrete Appl. Math. 82, 43\u201377 (1998)","journal-title":"Discrete Appl. Math."},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1137\/S0895480193253415","volume":"11","author":"A Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Chepoi, V.D., Voloshin, V.I.: Dually chordal graphs. SIAM J. Discrete Math. 11, 437\u2013455 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Eschen, E.M., Friese, E.: Efficient domination for some subclasses of $$P_6$$-free graphs in polynomial time. CoRR arXiv:1503.00091 (2015). Extended abstract. In: Mayr, E.W. (ed.) Proceedings of WG 2015. LNCS, vol. 9224, pp. 78\u201389 (2015)","DOI":"10.1007\/978-3-662-53174-7_6"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.dam.2016.08.019","volume":"223","author":"A Brandst\u00e4dt","year":"2017","unstructured":"Brandst\u00e4dt, A., Eschen, E.M., Friese, E., Karthick, T.: Efficient domination for classes of $$P_6$$-free graphs. Discrete Appl. Math. 223, 15\u201327 (2017)","journal-title":"Discrete Appl. Math."},{"key":"1_CR9","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/j.ipl.2014.09.024","volume":"115","author":"A Brandst\u00e4dt","year":"2015","unstructured":"Brandst\u00e4dt, A., Fi\u010dur, P., Leitert, A., Milani\u010d, M.: Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs. Inf. Process. Lett. 115, 256\u2013262 (2015)","journal-title":"Inf. Process. Lett."},{"key":"1_CR10","unstructured":"Brandst\u00e4dt, A., Giakoumakis, V.: Weighted efficient domination for $$(P_5+kP_2)$$-free graphs in polynomial time. CoRR arXiv:1407.4593v1 (2014)"},{"key":"1_CR11","unstructured":"Brandst\u00e4dt, A., Giakoumakis, V., Milani\u010d, M., Nevries, R.: Weighted efficient domination for $$F$$-free graphs. Manuscript (2014, submitted)"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/s00453-007-9045-2","volume":"52","author":"A Brandst\u00e4dt","year":"2008","unstructured":"Brandst\u00e4dt, A., Ho\u00e0ng, C.T.: Maximum induced matchings for chordal graphs in linear time. Algorithmica 52, 440\u2013447 (2008)","journal-title":"Algorithmica"},{"key":"1_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1007\/978-3-642-12200-2_56","volume-title":"LATIN 2010: Theoretical Informatics","author":"A Brandst\u00e4dt","year":"2010","unstructured":"Brandst\u00e4dt, A., Hundt, C., Nevries, R.: Efficient edge domination on hole-free graphs in polynomial time. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 650\u2013661. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-12200-2_56"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.dam.2015.07.032","volume":"201","author":"A Brandst\u00e4dt","year":"2016","unstructured":"Brandst\u00e4dt, A., Karthick, T.: Weighted efficient domination in two subclasses of $$P_6$$-free graphs. Discrete Appl. Math. 201, 38\u201346 (2016)","journal-title":"Discrete Appl. Math."},{"key":"1_CR15","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"publisher","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. SIAM Monographs on Discrete Mathematics and Applications, vol. 3. SIAM, Philadelphia (1999)"},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-642-35261-4_30","volume-title":"Algorithms and Computation","author":"A Brandst\u00e4dt","year":"2012","unstructured":"Brandst\u00e4dt, A., Leitert, A., Rautenbach, D.: Efficient dominating and edge dominating sets for graphs and hypergraphs. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 267\u2013277. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-35261-4_30. Full version: CoRR arXiv:1207.0953v2, [cs.DM] (2012)"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-642-40313-2_19","volume-title":"Mathematical Foundations of Computer Science 2013","author":"A Brandst\u00e4dt","year":"2013","unstructured":"Brandst\u00e4dt, A., Milani\u010d, M., Nevries, R.: New polynomial cases of the weighted efficient domination problem. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 195\u2013206. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40313-2_19. Full version: CoRR arXiv:1304.6255v1"},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/978-3-642-25591-5_12","volume-title":"Algorithms and Computation","author":"A Brandst\u00e4dt","year":"2011","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Dominating induced matchings for P\n          $$_7$$-free graphs in linear time. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 100\u2013109. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-25591-5_12. Full version: Algorithmica 68, 998\u20131018 (2014)"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Weighted efficient domination for $$P_6$$-free graphs in polynomial time. CoRR arXiv:1508.07733 (2015). Based on a manuscript by R. Mosca, Weighted Efficient Domination for $$P_6$$-Free Graphs, July 2015","DOI":"10.1007\/978-3-662-53536-3_4"},{"key":"1_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-662-53536-3_4","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A Brandst\u00e4dt","year":"2016","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Weighted efficient domination for $$P_6$$-free and for $$P_5$$-free graphs. In: Heggernes, P. (ed.) WG 2016. LNCS, vol. 9941, pp. 38\u201349. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53536-3_4. Full version: SIAM J. Discrete Math. 30(4) (2016)"},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1007\/s00453-016-0150-y","volume":"77","author":"A Brandst\u00e4dt","year":"2017","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Dominating induced matchings for $$P_8$$-free graphs in polynomial time. Algorithmica 77, 1283\u20131302 (2017)","journal-title":"Algorithmica"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Mosca, R.: On efficient domination for some classes of $$H$$-free chordal graphs. CoRR arXiv:1701.03414 (2017). Extended abstract in Conference Proceedings of LAGOS 2017, Marseille, Electron. Notes Discrete Math. 62, 57\u201362 (2017)","DOI":"10.1016\/j.endm.2017.10.011"},{"key":"1_CR23","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Dominating induced matchings in $$S_{1,2,4}$$-free graphs. CoRR arXiv:1706.09301 (2017)"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1137\/S0895480197326346","volume":"12","author":"HJ Broersma","year":"1999","unstructured":"Broersma, H.J., Kloks, T., Kratsch, D., M\u00fcller, H.: Independent sets in asteroidal-triple-free graphs. SIAM J. Discrete Math. 12, 276\u2013287 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0166-218X(92)90275-F","volume":"24","author":"K Cameron","year":"1989","unstructured":"Cameron, K.: Induced matchings. Discrete Appl. Math. 24, 97\u2013102 (1989)","journal-title":"Discrete Appl. Math."},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disc.2003.05.001","volume":"278","author":"K Cameron","year":"2004","unstructured":"Cameron, K.: Induced matchings in intersection graphs. Discrete Math. 278, 1\u20139 (2004)","journal-title":"Discrete Math."},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0012-365X(02)00803-8","volume":"266","author":"K Cameron","year":"2003","unstructured":"Cameron, K., Sritharan, R., Tang, Y.: Finding a maximum induced matching in weakly chordal graphs. Discrete Math. 266, 133\u2013142 (2003)","journal-title":"Discrete Math."},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"3060","DOI":"10.1016\/j.dam.2008.01.021","volume":"156","author":"DM Cardoso","year":"2008","unstructured":"Cardoso, D.M., Cerdeira, J.O., Delorme, C., Silva, P.C.: Efficient edge domination in regular graphs. Discrete Appl. Math. 156, 3060\u20133065 (2008)","journal-title":"Discrete Appl. Math."},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/j.dam.2010.03.011","volume":"159","author":"DM Cardoso","year":"2011","unstructured":"Cardoso, D.M., Korpelainen, N., Lozin, V.V.: On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Appl. Math. 159, 521\u2013531 (2011)","journal-title":"Discrete Appl. Math."},{"key":"1_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-642-02029-2_8","volume-title":"Graph Theory, Computational Intelligence and Thought","author":"DM Cardoso","year":"2009","unstructured":"Cardoso, D.M., Lozin, V.V.: Dominating induced matchings. In: Lipshteyn, M., Levit, V.E., McConnell, R.M. (eds.) Graph Theory, Computational Intelligence and Thought. LNCS, vol. 5420, pp. 77\u201386. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02029-2_8"},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0166-218X(97)80001-7","volume":"80","author":"M-S Chang","year":"1997","unstructured":"Chang, M.-S.: Weighted domination of co-comparability graphs. Discrete Appl. Math. 80, 135\u2013148 (1997)","journal-title":"Discrete Appl. Math."},{"key":"1_CR32","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0166-218X(03)00390-1","volume":"132","author":"J-M Chang","year":"2004","unstructured":"Chang, J.-M.: Induced matchings in asteroidal-triple-free graphs. Discrete Appl. Math. 132, 67\u201378 (2004)","journal-title":"Discrete Appl. Math."},{"key":"1_CR33","first-page":"161","volume":"67","author":"J-M Chang","year":"2003","unstructured":"Chang, J.-M., Ho, C.-W., Ko, M.-T.: Powers of asteroidal-triple-free graphs with applications. Ars Comb. 67, 161\u2013173 (2003)","journal-title":"Ars Comb."},{"key":"1_CR34","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0020-0190(93)90147-2","volume":"48","author":"M-S Chang","year":"1993","unstructured":"Chang, M.-S., Liu, Y.C.: Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs. Inf. Process. Lett. 48, 205\u2013210 (1993)","journal-title":"Inf. Process. Lett."},{"key":"1_CR35","first-page":"549","volume":"11","author":"M-S Chang","year":"1994","unstructured":"Chang, M.-S., Liu, Y.C.: Polynomial algorithms for the weighted perfect domination problems on interval and circular-arc graphs. J. Inf. Sci. Eng. 11, 549\u2013568 (1994)","journal-title":"J. Inf. Sci. Eng."},{"key":"1_CR36","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0166-218X(94)00067-3","volume":"63","author":"GJ Chang","year":"1995","unstructured":"Chang, G.J., Pandu Rangan, C., Coorg, S.R.: Weighted independent perfect domination on co-comparability graphs. Discrete Appl. Math. 63, 215\u2013222 (1995)","journal-title":"Discrete Appl. Math."},{"key":"1_CR37","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"1_CR38","doi-asserted-by":"publisher","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."},{"key":"1_CR39","first-page":"67","volume":"4","author":"FF Dragan","year":"1992","unstructured":"Dragan, F.F., Prisacaru, C.F., Chepoi, V.D.: Location problems in graphs and the Helly property. Discrete Math. 4, 67\u201373 (1992). Moscow, (in Russian), the full version appeared as preprint: Dragan, F.F., Prisacaru, C.F., Chepoi, V.D.: r-domination and p-center problems on graphs: special solution methods and graphs for which this method is usable, Kishinev State University, preprint MoldNIINTI, N. 948-M88 (1987), (in Russian)","journal-title":"Discrete Math."},{"key":"1_CR40","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Canad. J. Math. 17, 449\u2013467 (1965)","journal-title":"Canad. J. Math."},{"key":"1_CR41","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.dam.2013.08.011","volume":"162","author":"E Eschen","year":"2014","unstructured":"Eschen, E., Wang, X.: Algorithms for unipolar and generalized split graphs. Discrete Appl. Math. 162, 195\u2013201 (2014)","journal-title":"Discrete Appl. Math."},{"key":"1_CR42","first-page":"141","volume":"3","author":"MR Fellows","year":"1991","unstructured":"Fellows, M.R., Hoover, M.N.: Perfect domination. Australas. J. Comb. 3, 141\u2013150 (1991)","journal-title":"Australas. J. Comb."},{"key":"1_CR43","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0166-218X(95)00062-V","volume":"63","author":"C Flotow","year":"1995","unstructured":"Flotow, C.: On powers of $$m$$-trapezoid graphs. Discrete Appl. Math. 63, 187\u2013192 (1995)","journal-title":"Discrete Appl. Math."},{"key":"1_CR44","unstructured":"Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs. In: Proceedings of the 5th British Combinatorial Conference (Aberdeen 1975), Congressus Numerantium, No. XV, pp. 211\u2013226 (1976)"},{"key":"1_CR45","first-page":"239","volume":"89","author":"G Fricke","year":"1992","unstructured":"Fricke, G., Laskar, R.: Strong matchings on trees. Congr. Numer. 89, 239\u2013243 (1992)","journal-title":"Congr. Numer."},{"key":"1_CR46","unstructured":"Friese, E.: Das Efficient-Domination-Problem auf $$P_6$$-freien Graphen. Master thesis. University of Rostock, Germany (2013). (in German)"},{"key":"1_CR47","volume-title":"Computers and Intractability \u2013 A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability \u2013 A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"1_CR48","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0020-0190(00)00025-9","volume":"73","author":"F Gavril","year":"2000","unstructured":"Gavril, F.: Maximum weight independent sets and cliques in intersection graphs of filaments. Inf. Process. Lett. 73, 181\u2013188 (2000)","journal-title":"Inf. Process. Lett."},{"key":"1_CR49","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0166-218X(93)90223-B","volume":"44","author":"MC Golumbic","year":"1993","unstructured":"Golumbic, M.C., Laskar, R.: Irredundancy in circular arc graphs. Discrete Appl. Math. 44, 79\u201389 (1993)","journal-title":"Discrete Appl. Math."},{"key":"1_CR50","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0166-218X(99)00194-8","volume":"101","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Lewenstein, M.: New results on induced matchings. Discrete Appl. Math. 101, 157\u2013165 (2000)","journal-title":"Discrete Appl. Math."},{"key":"1_CR51","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0020-0190(93)90084-M","volume":"48","author":"DL Grinstead","year":"1993","unstructured":"Grinstead, D.L., Slater, P.L., Sherwani, N.A., Holmes, N.D.: Efficient edge domination problems in graphs. Inf. Process. Lett. 48, 221\u2013228 (1993)","journal-title":"Inf. Process. Lett."},{"key":"1_CR52","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169\u2013197 (1981). Corrigendum. Combinatorica 4, 291\u2013295 (1984)","journal-title":"Combinatorica"},{"key":"1_CR53","unstructured":"Hayward, R.B., Spinrad, J.P., Sritharan, R.: Weakly chordal graph algorithms via handles. In: Proceedings of the 11th Symposium on Discrete Algorithms (SODA), pp. 42\u201349 (2000)"},{"key":"1_CR54","doi-asserted-by":"crossref","unstructured":"Hayward, R.B., Spinrad, J.P., Sritharan, R.: Improved algorithms for weakly chordal graphs. ACM Trans. Algorithms 3, Article No. 14 (2007)","DOI":"10.1145\/1240233.1240237"},{"key":"1_CR55","unstructured":"Hertz, A., Lozin, V.V., Ries, B., Zamaraev, V., de Werra, D.: Dominating induced matchings in graphs containing no long claw. CoRR arXiv:1505.02558 (2015)"},{"key":"1_CR56","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"1_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-319-14974-5_8","volume-title":"Algorithms and Discrete Applied Mathematics","author":"T Karthick","year":"2015","unstructured":"Karthick, T.: New polynomial case for efficient domination in P\n          $$_6$$-free graphs. In: Ganguly, S., Krishnamurti, R. (eds.) CALDAM 2015. LNCS, vol. 8959, pp. 81\u201388. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-14974-5_8"},{"key":"1_CR58","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00453-003-1035-4","volume":"37","author":"D Kobler","year":"2003","unstructured":"Kobler, D., Rotics, U.: Finding maximum induced matchings in subclasses of claw-free and $$P_5$$-free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica 37, 327\u2013346 (2003)","journal-title":"Algorithmica"},{"key":"1_CR59","unstructured":"K\u00f6hler, E.: Graphs without asteroidal triples. Ph.D. thesis, Technical University of Berlin (1999)"},{"key":"1_CR60","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.jda.2013.11.002","volume":"26","author":"N Korpelainen","year":"2014","unstructured":"Korpelainen, N., Lozin, V.V., Purcell, C.: Dominating induced matchings in graphs without a skew star. J. Discrete Algorithms 26, 45\u201355 (2014)","journal-title":"J. Discrete Algorithms"},{"key":"1_CR61","unstructured":"Kratochv\u00edl, J.: Perfect codes in general graphs, Rozpravy \u010ceskoslovensk\u00e9 Akad. V\u011bd \u0158ada Mat. P\u0159\u00edrod V$${\\rm \\check{d}}$$ 7. Akademia, Praha (1991)"},{"key":"1_CR62","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0012-365X(94)90026-4","volume":"133","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J.: Regular codes in regular graphs are difficult. Discrete Math. 133, 191\u2013205 (1994)","journal-title":"Discrete Math."},{"key":"1_CR63","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/j.dam.2011.08.027","volume":"160","author":"CM Krishnamurthy","year":"2012","unstructured":"Krishnamurthy, C.M., Sritharan, R.: Maximum induced matching problem on HHD-free graphs. Discrete Appl. Math. 160, 224\u2013230 (2012)","journal-title":"Discrete Appl. Math."},{"key":"1_CR64","unstructured":"Leitert, A.: Das dominating induced matching problem f\u00fcr azyklische Hypergraphen. Diploma thesis, University of Rostock, Germany (2012)"},{"key":"1_CR65","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BFb0045090","volume-title":"Computing and Combinatorics","author":"YD Liang","year":"1997","unstructured":"Liang, Y.D., Lu, C.L., Tang, C.Y.: Efficient domination on permutation graphs and trapezoid graphs. In: Jiang, T., Lee, D.T. (eds.) COCOON 1997. LNCS, vol. 1276, pp. 232\u2013241. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/BFb0045090"},{"key":"1_CR66","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/3-540-49381-6_29","volume-title":"Algorithms and Computation","author":"Y-L Lin","year":"1998","unstructured":"Lin, Y.-L.: Fast algorithms for independent domination and efficient domination in trapezoid graphs. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol. 1533, pp. 267\u2013275. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/3-540-49381-6_29"},{"issue":"10","key":"1_CR67","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.ipl.2014.04.012","volume":"114","author":"MC Lin","year":"2014","unstructured":"Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: Fast algorithms for some dominating induced matching problems. Inf. Process. Lett. 114(10), 524\u2013528 (2014)","journal-title":"Inf. Process. Lett."},{"key":"1_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-642-54423-1_35","volume-title":"LATIN 2014: Theoretical Informatics","author":"MC Lin","year":"2014","unstructured":"Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: O(n) time algorithms for dominating induced matching problems. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 399\u2013408. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54423-1_35"},{"key":"1_CR69","doi-asserted-by":"crossref","unstructured":"Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: Efficient and perfect domination on circular-arc graphs. CoRR arXiv:1502.01523v1 (2015). Electron. Notes Discrete Math. 50, 307\u2013312 (2015)","DOI":"10.1016\/j.endm.2015.07.051"},{"key":"1_CR70","doi-asserted-by":"crossref","unstructured":"Livingston, M., Stout, Q.: Distributing resources in hypercube computers. In: Proceedings of Third Conference on Hypercube Concurrent Computers and Applications, pp. 222\u2013231 (1988)","DOI":"10.1145\/62297.62324"},{"key":"1_CR71","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Pilipczuk, M., van Leeuwen, E.J.: Independence and efficient domination on $$P_6$$-free graphs. CoRR arXiv:1507.02163v2 (2015). Conference Proceedings of SODA 2016, pp. 1784\u20131803","DOI":"10.1137\/1.9781611974331.ch124"},{"key":"1_CR72","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in $$P_5$$-free graphs in polynomial time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 570\u2013581 (2014)","DOI":"10.1137\/1.9781611973402.43"},{"key":"1_CR73","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0012-365X(72)90006-4","volume":"2","author":"L Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2, 253\u2013267 (1972)","journal-title":"Discrete Math."},{"key":"1_CR74","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0166-218X(01)00198-6","volume":"119","author":"CL Lu","year":"2002","unstructured":"Lu, C.L., Ko, M.-T., Tang, C.Y.: Perfect edge domination and efficient edge domination in graphs. Discrete Appl. Math. 119, 227\u2013250 (2002)","journal-title":"Discrete Appl. Math."},{"key":"1_CR75","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0166-218X(98)00057-2","volume":"87","author":"CL Lu","year":"1998","unstructured":"Lu, C.L., Tang, C.Y.: Solving the weighted efficient edge domination problem on bipartite permutation graphs. Discrete Appl. Math. 87, 203\u2013211 (1998)","journal-title":"Discrete Appl. Math."},{"key":"1_CR76","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0166-218X(01)00184-6","volume":"117","author":"CL Lu","year":"2002","unstructured":"Lu, C.L., Tang, C.Y.: Weighted efficient domination problem on some perfect graphs. Discrete Appl. Math. 117, 163\u2013182 (2002)","journal-title":"Discrete Appl. Math."},{"key":"1_CR77","unstructured":"Milani\u010d, M.: A hereditary view on efficient domination. In: Proceedings of the 10th Cologne-Twente Workshop. Extended Abstract, pp. 203\u2013206 (2011)"},{"key":"1_CR78","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1002\/jgt.21685","volume":"73","author":"M Milani\u010d","year":"2013","unstructured":"Milani\u010d, M.: Hereditary efficiently dominatable graphs. J. Graph Theory 73, 400\u2013424 (2013)","journal-title":"J. Graph Theory"},{"key":"1_CR79","unstructured":"Nevries, R.: Efficient domination and polarity. Ph.D. thesis, University of Rostock (2014)"},{"key":"1_CR80","first-page":"147","volume":"34","author":"A Raychaudhuri","year":"1992","unstructured":"Raychaudhuri, A.: On powers of strongly chordal and circular-arc graphs. Ars Combin. 34, 147\u2013160 (1992)","journal-title":"Ars Combin."},{"key":"1_CR81","first-page":"83","volume":"112","author":"CB Smart","year":"1995","unstructured":"Smart, C.B., Slater, P.J.: Complexity results for closed neighborhood order parameters. Congr. Numer. 112, 83\u201396 (1995)","journal-title":"Congr. Numer."},{"key":"1_CR82","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","volume":"15","author":"LJ Stockmeyer","year":"1982","unstructured":"Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett. 15, 14\u201319 (1982)","journal-title":"Inf. Process. Lett."},{"key":"1_CR83","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: Proceedings of the 44th Symposium on Theory of Computing, STOC 2012, pp. 887\u2013898. ACM, New York (2012)","DOI":"10.1145\/2213977.2214056"},{"key":"1_CR84","unstructured":"Yen, C.-C.: Algorithmic aspects of perfect domination. Ph.D. thesis, Institute of Information Science, National Tsing Hua University, Taiwan (1992)"},{"key":"1_CR85","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0166-218X(94)00138-4","volume":"66","author":"C-C Yen","year":"1996","unstructured":"Yen, C.-C., Lee, R.C.T.: The weighted perfect domination problem and its variants. Discrete Appl. Math. 66, 147\u2013160 (1996)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-74180-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:50:24Z","timestamp":1709826624000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-74180-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319741796","9783319741802"],"references-count":85,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-74180-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"16 January 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Guwahati","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 February 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 February 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.iitg.ac.in\/caldam2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}