{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T13:28:52Z","timestamp":1770902932753,"version":"3.50.1"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032171559","type":"print"},{"value":"9783032171566","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-17156-6_34","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T12:36:32Z","timestamp":1770899792000},"page":"457-470","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Hardness and\u00a0Approximation Results on\u00a0the\u00a0Total Dominating Set Problem"],"prefix":"10.1007","author":[{"given":"Sasmita","family":"Rout","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gautam Kumar","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"issue":"6","key":"34_CR1","first-page":"253","volume":"4","author":"M Atapour","year":"2009","unstructured":"Atapour, M., Soltankhah, N.: On total dominating sets in graphs. Int. J. Contemp. Math. Sciences 4(6), 253\u2013257 (2009)","journal-title":"Int. J. Contemp. Math. Sciences"},{"issue":"2","key":"34_CR2","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0166-218X(94)00138-4","volume":"66","author":"Y Chain-Chin","year":"1996","unstructured":"Chain-Chin, Y., Lee, R.C.: The weighted perfect domination problem and its variants. Discret. Appl. Math. 66(2), 147\u2013160 (1996)","journal-title":"Discret. Appl. Math."},{"key":"34_CR3","first-page":"189","volume":"58","author":"M Chellali","year":"2006","unstructured":"Chellali, M., Haynes, T.W.: A note on the total domination number of a tree. J. Comb. Math. Comb. Comput. 58, 189\u2013193 (2006)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"1\u20133","key":"34_CR4","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0012-365X(02)00447-8","volume":"260","author":"EJ Cockayne","year":"2003","unstructured":"Cockayne, E.J., Henning, M.A., Mynhardt, C.M.: Vertices contained in all or in no minimum total dominating set of a tree. Discret. Math. 260(1\u20133), 37\u201344 (2003)","journal-title":"Discret. Math."},{"issue":"3","key":"34_CR5","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1002\/net.3230100304","volume":"10","author":"EJ Cockayne","year":"1980","unstructured":"Cockayne, E.J., Dawes, R., Hedetniemi, S.T.: Total domination in graphs. Networks 10(3), 211\u2013219 (1980)","journal-title":"Networks"},{"issue":"1\u20133","key":"34_CR6","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","volume":"278","author":"EJ Cockayne","year":"2004","unstructured":"Cockayne, E.J., Dreyer, P.A., Jr., Hedetniemi, S.M., Hedetniemi, S.T.: Roman domination in graphs. Discret. Math. 278(1\u20133), 11\u201322 (2004)","journal-title":"Discret. Math."},{"key":"34_CR7","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, 4 edn. (2022)"},{"issue":"5","key":"34_CR8","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0020-0190(90)90147-P","volume":"36","author":"P Damaschke","year":"1990","unstructured":"Damaschke, P., M\u00fcller, H., Kratsch, D.: Domination in convex and chordal bipartite graphs. Inf. Process. Lett. 36(5), 231\u2013236 (1990)","journal-title":"Inf. Process. Lett."},{"key":"34_CR9","unstructured":"DeLaVina, E., Liu, Q., Pepper, R., Waller, B., West, D.B.: Some conjectures of graffiti.pc on total domination. Congressus Numerantium 185, 81 (2007)"},{"key":"34_CR10","first-page":"237","volume":"78","author":"M Dorfling","year":"2006","unstructured":"Dorfling, M., Goddard, W., Henning, M.A.: Domination in planar graphs with small diameter ii. Ars Combin. 78, 237\u2013255 (2006)","journal-title":"Ars Combin."},{"issue":"2","key":"34_CR11","doi-asserted-by":"publisher","first-page":"233","DOI":"10.7151\/dmgt.1172","volume":"22","author":"TW Haynes","year":"2002","unstructured":"Haynes, T.W., Henning, M.A.: Trees with unique minimum total dominating sets. Discussiones Mathematicae Graph Theory 22(2), 233\u2013246 (2002)","journal-title":"Discussiones Mathematicae Graph Theory"},{"issue":"8","key":"34_CR12","doi-asserted-by":"publisher","first-page":"1293","DOI":"10.1016\/j.dam.2006.01.002","volume":"154","author":"TW Haynes","year":"2006","unstructured":"Haynes, T.W., Henning, M.A., Howard, J.: Locating and total dominating sets in trees. Discret. Appl. Math. 154(8), 1293\u20131300 (2006)","journal-title":"Discret. Appl. Math."},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"Jallu, R.K., Jena, S.K., Das, G.K.: Liar\u2019s dominating set in unit disk graphs. In: International Computing and Combinatorics Conference, pp. 516\u2013528. Springer (2018)","DOI":"10.1007\/978-3-319-94776-1_43"},{"key":"34_CR14","unstructured":"Jena, S.K., Das, G.K.: Total domination in geometric unit disk graphs. In: Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021, August 10-12, 2021, pp. 219\u2013227 (2021)"},{"issue":"1","key":"34_CR15","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0166-218X(93)90178-Q","volume":"42","author":"JM Keil","year":"1993","unstructured":"Keil, J.M.: The complexity of domination problems in circle graphs. Discret. Appl. Math. 42(1), 51\u201363 (1993)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"34_CR16","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1137\/0605040","volume":"5","author":"R Laskar","year":"1984","unstructured":"Laskar, R., Pfaff, J., Hedetniemi, S.M., Hedetniemi, S.T.: On the algorithmic complexity of total domination. SIAM J. Algebraic Discrete Methods 5(3), 420\u2013425 (1984)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"2","key":"34_CR17","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"34_CR18","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"MV Marathe","year":"1995","unstructured":"Marathe, M.V., Breu, H., Hunt, H.B., III., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks 25(2), 59\u201368 (1995)","journal-title":"Networks"},{"key":"34_CR19","unstructured":"Pfaff, J., Laskar, R., Hedetniemi, S.: NP-completeness of total and connected domination and irredundance for bipartite graphs. technicial report 428, dept. math. Sciences, Clemson University (1983)"},{"key":"34_CR20","doi-asserted-by":"crossref","unstructured":"Rout, S., Das, G.K.: Semi-total domination in unit disk graphs. In: Conference on Algorithms and Discrete Applied Mathematics, pp. 117\u2013129. Springer (2024)","DOI":"10.1007\/978-3-031-52213-0_9"},{"key":"34_CR21","doi-asserted-by":"crossref","unstructured":"Rout, S., Mishra, P.K., Das, G.K.: Total Roman domination and total domination in unit disk graphs. Commun. Combinatorics Optim. (2024)","DOI":"10.1007\/978-3-031-52213-0_9"},{"issue":"4","key":"34_CR22","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/s00493-007-2020-3","volume":"27","author":"S Thomass\u00e9","year":"2007","unstructured":"Thomass\u00e9, S., Yeo, A.: Total domination of graphs and small transversals of hypergraphs. Combinatorica 27(4), 473\u2013487 (2007)","journal-title":"Combinatorica"},{"issue":"2","key":"34_CR23","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"100","author":"LG Valiant","year":"1981","unstructured":"Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Comput. 100(2), 135\u2013140 (1981)","journal-title":"IEEE Trans. Comput."}],"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-032-17156-6_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T12:36:37Z","timestamp":1770899797000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17156-6_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032171559","9783032171566"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17156-6_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 February 2026","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":"Dharwad","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":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/caldam2026.iitdh.ac.in\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}