{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T10:39:03Z","timestamp":1725878343683},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319519623"},{"type":"electronic","value":"9783319519630"}],"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":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-51963-0_26","type":"book-chapter","created":{"date-parts":[[2017,1,10]],"date-time":"2017-01-10T06:17:39Z","timestamp":1484029059000},"page":"336-349","source":"Crossref","is-referenced-by-count":4,"title":["Parameterized and Exact Algorithms for Class Domination Coloring"],"prefix":"10.1007","author":[{"given":"R.","family":"Krithika","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashutosh","family":"Rai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prafullkumar","family":"Tale","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,1,11]]},"reference":[{"issue":"4","key":"26_CR1","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33(4), 461\u2013493 (2002)","journal-title":"Algorithmica"},{"issue":"4","key":"26_CR2","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1007\/s00453-008-9204-0","volume":"54","author":"N Alon","year":"2009","unstructured":"Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica 54(4), 544\u2013556 (2009)","journal-title":"Algorithmica"},{"issue":"2","key":"26_CR3","doi-asserted-by":"crossref","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)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"26_CR4","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0020-0190(96)00190-1","volume":"61","author":"A Blum","year":"1997","unstructured":"Blum, A., Karger, D.R.: An $$\\tilde{\\cal{O}}(n^{3\/14})$$ -coloring algorithm for $$3$$ -colorable graphs. Inf. Process. Lett. 61(1), 49\u201353 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"26_CR5","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discrete Appl. Math. 127(3), 415\u2013429 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"26_CR6","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s00373-010-1012-z","volume":"28","author":"M Chellali","year":"2012","unstructured":"Chellali, M., Maffray, F.: Dominator Colorings in Some Classes of Graphs. Graph. Comb. 28(1), 97\u2013107 (2012)","journal-title":"Graph. Comb."},{"issue":"40\u201342","key":"26_CR7","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., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"26_CR8","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0166-218X(88)90086-8","volume":"22","author":"DG Corneil","year":"1989","unstructured":"Corneil, D.G., Fonlupt, J.: The complexity of generalized clique covering. Discrete Appl. Math. 22(2), 109\u2013118 (1989)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"26_CR9","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"26_CR10","first-page":"257","volume":"ITA 26","author":"B Courcelle","year":"1992","unstructured":"Courcelle, B.: The monadic second-order logic of graphs III: tree-decompositions. Minor Complex. Issues ITA 26, 257\u2013286 (1992)","journal-title":"Minor Complex. Issues"},{"key":"26_CR11","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., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015)"},{"key":"26_CR12","volume-title":"Graph Theory","author":"R Diestel","year":"2006","unstructured":"Diestel, R.: Graph Theory. Springer, Heidelberg (2006)"},{"key":"26_CR13","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. Springer, London (2013)"},{"issue":"1","key":"26_CR14","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ipl.2008.09.017","volume":"109","author":"RG Downey","year":"2008","unstructured":"Downey, R.G., Fellows, M.R., McCartin, C., Rosamond, F.A.: Parameterized approximation of dominating set problems. Inf. Process. Lett. 109(1), 68\u201370 (2008)","journal-title":"Inf. Process. Lett."},{"key":"26_CR15","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"26_CR16","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 and Company, New York (1979)"},{"issue":"1","key":"26_CR17","doi-asserted-by":"crossref","first-page":"9:1","DOI":"10.1145\/1644015.1644024","volume":"6","author":"S Gaspers","year":"2009","unstructured":"Gaspers, S., Kratsch, D., Liedloff, M., Todinca, I.: Exponential time algorithms for the minimum dominating set problem on some graph classes. ACM Trans. Algorithms 6(1), 9:1\u201321 (2009)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"26_CR18","first-page":"29","volume":"14","author":"S Gaspers","year":"2012","unstructured":"Gaspers, S., Liedloff, M.: A branch-and-reduce algorithm for finding a minimum independent dominating set. Discrete Math. Theor. Comput. Sci. 14(1), 29\u201342 (2012)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Gera, R.: On dominator colorings in graphs. In: Graph Theory Notes of New York LII, pp. 25\u201330 (2007)","key":"26_CR19","DOI":"10.1109\/ITNG.2007.142"},{"issue":"7\u20139","key":"26_CR20","first-page":"1932","volume":"181","author":"R Gera","year":"2006","unstructured":"Gera, R., Rasmussen, C., Horton, S.: Dominator colorings and safe clique partitions. Congressus Numerantium 181(7\u20139), 1932 (2006)","journal-title":"Congressus Numerantium"},{"issue":"1","key":"26_CR21","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1006\/inco.1998.2754","volume":"150","author":"S Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Improved methods for approximating node weighted steiner trees and connected dominating sets. Inf. Comput. 150(1), 57\u201374 (1999)","journal-title":"Inf. Comput."},{"issue":"8","key":"26_CR22","doi-asserted-by":"crossref","first-page":"1108","DOI":"10.1109\/TMC.2010.55","volume":"9","author":"D Kim","year":"2010","unstructured":"Kim, D., Zhang, Z., Li, X., Wang, W., Wu, W., Du, D.Z.: A better approximation algorithm for computing connected dominating sets in unit ball graphs. IEEE Trans. Mob. Comput. 9(8), 1108\u20131118 (2010)","journal-title":"IEEE Trans. Mob. Comput."},{"key":"26_CR23","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1007\/978-0-387-30162-4_132","volume-title":"Encyclopedia of Algorithms","author":"D Kratsch","year":"2008","unstructured":"Kratsch, D.: Exact algorithms for dominating set. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms, pp. 284\u2013286. Springer, New York (2008)"},{"issue":"3","key":"26_CR24","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"E Lawler","year":"1976","unstructured":"Lawler, E.: A note on the complexity of the chromatic number problem. Inf. Process. Lett. 5(3), 66\u201367 (1976)","journal-title":"Inf. Process. Lett."},{"key":"26_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1007\/978-3-642-15763-9_48","volume-title":"Distributed Computing","author":"C Lenzen","year":"2010","unstructured":"Lenzen, C., Wattenhofer, R.: Minimum dominating set approximation in graphs of bounded arboricity. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 510\u2013524. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-15763-9_48"},{"issue":"2","key":"26_CR26","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":"26_CR27","doi-asserted-by":"crossref","first-page":"15:1","DOI":"10.1145\/2566616","volume":"11","author":"D Lokshtanov","year":"2014","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. ACM Trans. Algorithms 11(2), 15:1\u201315:31 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"26_CR28","first-page":"61","volume":"2","author":"VV Lozin","year":"2007","unstructured":"Lozin, V.V., Kaminski, M.: Coloring edges and vertices of graphs without short or long cycles. Contrib. Discrete Math. 2(1), 61\u201366 (2007)","journal-title":"Contrib. Discrete Math."},{"key":"26_CR29","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"unstructured":"Panolan, F., Philip, G., Saurabh, S.: B-Chromatic number: beyond NP-hardness. In: 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, pp. 389\u2013401 (2015)","key":"26_CR30"},{"issue":"2","key":"26_CR31","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s00453-007-9148-9","volume":"52","author":"V Raman","year":"2008","unstructured":"Raman, V., Saurabh, S.: Short cycles make w-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica 52(2), 203\u2013225 (2008)","journal-title":"Algorithmica"},{"issue":"17","key":"26_CR32","doi-asserted-by":"crossref","first-page":"2147","DOI":"10.1016\/j.dam.2011.07.001","volume":"159","author":"JMM Rooij van","year":"2011","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Exact algorithms for dominating set. Discrete Appl. Math. 159(17), 2147\u20132164 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"3\u20134","key":"26_CR33","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A Sch\u00f6nhage","year":"1971","unstructured":"Sch\u00f6nhage, A., Strassen, V.: Schnelle Multiplikation grosser Zahlen. Computing 7(3\u20134), 281\u2013292 (1971)","journal-title":"Computing"},{"unstructured":"Shalu, M.A., Sandhya, T.P.: Personal communication (2016)","key":"26_CR34"},{"key":"26_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-319-29221-2_29","volume-title":"Algorithms and Discrete Applied Mathematics","author":"MA Shalu","year":"2016","unstructured":"Shalu, M.A., Sandhya, T.P.: The cd-coloring of graphs. In: Govindarajan, S., Maheshwari, A. (eds.) CALDAM 2016. LNCS, vol. 9602, pp. 337\u2013348. Springer, Heidelberg (2016). doi: 10.1007\/978-3-319-29221-2_29"},{"key":"26_CR36","first-page":"233","volume":"12","author":"YB Venkatakrishnan","year":"2010","unstructured":"Venkatakrishnan, Y.B., Swaminathan, V.: Color class domination number of middle graph and center graph of K $$_{1, n}$$ , C $$_n$$ , P $$_n$$ . Adv. Model. Optim. 12, 233\u2013237 (2010)","journal-title":"Adv. Model. Optim."},{"issue":"2","key":"26_CR37","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"M Yannakakis","year":"1987","unstructured":"Yannakakis, M., Gavril, F.: The maximum $$k$$ -colorable subgraph problem for chordal graphs. Inf. Process. Lett. 24(2), 133\u2013137 (1987)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2017: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-51963-0_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T10:03:50Z","timestamp":1568714630000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-51963-0_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319519623","9783319519630"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-51963-0_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}