{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:10Z","timestamp":1740122410183,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,22]],"date-time":"2022-11-22T00:00:00Z","timestamp":1669075200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,11,22]],"date-time":"2022-11-22T00:00:00Z","timestamp":1669075200000},"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":["J Comb Optim"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s10878-022-00932-4","type":"journal-article","created":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T05:13:38Z","timestamp":1669180418000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A simple optimal algorithm for k-tuple dominating problem in interval graphs"],"prefix":"10.1007","volume":"45","author":[{"given":"Peng","family":"Li","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5784-7208","authenticated-orcid":false,"given":"Aifa","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Jianhui","family":"Shang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,22]]},"reference":[{"key":"932_CR1","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.ipl.2018.06.007","volume":"138","author":"G Argiroffo","year":"2018","unstructured":"Argiroffo G, Leoni V, Torres P (2018) Complexity of k-tuple total and total k-dominations for some subclasses of bipartite graphs. Inf Process Lett 138:75\u201380","journal-title":"Inf Process Lett"},{"key":"932_CR2","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s12190-013-0656-2","volume":"43","author":"SC Barman","year":"2013","unstructured":"Barman SC, Mondal S, Pal M (2013) Minimum 2-tuple dominating set of permutation graphs. J Appl Math Comput 43:133\u2013150","journal-title":"J Appl Math Comput"},{"key":"932_CR3","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2013.01.011","volume":"511","author":"R Belmonte","year":"2013","unstructured":"Belmonte R, Vatshelle M (2013) Graph classes with structured neighborhoods and algorithmic applications. Theor Comput Sci 511:54\u201365","journal-title":"Theor Comput Sci"},{"key":"932_CR4","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth KS, Lueker GS (1976) Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J Comput Syst Sci 13:335\u2013379","journal-title":"J Comput Syst Sci"},{"key":"932_CR5","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2013.01.009","volume":"511","author":"BM Bui-Xuan","year":"2013","unstructured":"Bui-Xuan BM, Telle JA, Vatshelle M (2013) Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor Comput Sci 511:66\u201376","journal-title":"Theor Comput Sci"},{"issue":"2","key":"932_CR6","doi-asserted-by":"publisher","first-page":"263","DOI":"10.7151\/dmgt.1603","volume":"32","author":"M Chellali","year":"2012","unstructured":"Chellali M, Meddah N (2012) Trees with equal 2-domination and 2-independence numbers. Discuss Math Graph Theory 32(2):263\u2013270","journal-title":"Discuss Math Graph Theory"},{"issue":"1","key":"932_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-011-1040-3","volume":"28","author":"M Chellali","year":"2012","unstructured":"Chellali M, Favaron O, Hansberg A, Volkmann L (2012) k-domination and k-independence in graphs, a survey. Graphs Comb 28(1):1\u201355","journal-title":"Graphs Comb"},{"key":"932_CR8","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.tcs.2019.06.007","volume":"795","author":"N Chiarelli","year":"2019","unstructured":"Chiarelli N, Hartinger TR, Leoni VA, Pujato MIL, Milanic M (2019) New algorithms for weighted $$k$$-domination and total $$k$$-domination problems in proper interval graphs. Theor Comput Sci 795:128\u2013141","journal-title":"Theor Comput Sci"},{"issue":"6","key":"932_CR9","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1016\/j.dam.2012.10.007","volume":"161","author":"F Cicalese","year":"2013","unstructured":"Cicalese F, Milanic M, Vaccaro U (2013) On the approximability and exact algorithms for vector domination and related problems in graphs. Discrete Appl Math 161(6):750\u2013767","journal-title":"Discrete Appl Math"},{"key":"932_CR10","doi-asserted-by":"publisher","first-page":"1905","DOI":"10.1137\/S0895480100373455","volume":"23","author":"DG Corneil","year":"2009","unstructured":"Corneil DG, Olariu S, Stewart L (2009) The LBFS structure and recognition of interval graphs. SIAM J Discrete Math 23:1905\u20131953","journal-title":"SIAM J Discrete Math"},{"issue":"1","key":"932_CR11","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1002\/jgt.20279","volume":"57","author":"O Favaron","year":"2008","unstructured":"Favaron O, Hansberg A, Volkmann L (2008) On k-domination and minimum degree in graphs. J Graph Theory 57(1):33\u201340","journal-title":"J Graph Theory"},{"key":"932_CR12","unstructured":"Fink JF, Jacobson MS (1984) n-domination in graphs, Graph Theory With Applications to Algorithms and Computer Science, Kalamazoo, Mich., Wiley Interscience Publisher Wiley, New York 1985, pp 283\u2013300"},{"key":"932_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90042-1","volume-title":"Interval orders and interval graphs: a study of partially ordered sets","author":"PC Fishburn","year":"1985","unstructured":"Fishburn PC (1985) Interval orders and interval graphs: a study of partially ordered sets. Wiley, New York"},{"key":"932_CR14","volume-title":"Algorithmic graph theory and perfect graphs. Annals of discrete mathematics","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs. Annals of discrete mathematics, vol 57, 2nd edn. Elsevier, Amsterdam","edition":"2"},{"issue":"10\u201311","key":"932_CR15","doi-asserted-by":"publisher","first-page":"1472","DOI":"10.1016\/j.dam.2013.02.008","volume":"161","author":"A Hansberg","year":"2013","unstructured":"Hansberg A, Pepper R (2013) On k-domination and j-independence in graphs. Discrete Appl Math 161(10\u201311):1472\u20131480","journal-title":"Discrete Appl Math"},{"key":"932_CR16","first-page":"201","volume":"55","author":"F Harary","year":"2000","unstructured":"Harary F, Haynes TW (2000) Double domination in graphs. Ars Comb 55:201\u2013213","journal-title":"Ars Comb"},{"key":"932_CR17","volume-title":"Domination in graphs: advanced topics","author":"TW Haynes","year":"1998","unstructured":"Haynes TW, Hedetniemi ST, Slater PJ (1998) Domination in graphs: advanced topics. Marcel Dekker Inc, New York"},{"key":"932_CR18","volume-title":"Fundamentals of domination in graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes TW, Hedetniemi ST, Slater PJ (1998) Fundamentals of domination in graphs. Marcel Dekker Inc, New York"},{"key":"932_CR19","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1016\/j.dam.2010.01.009","volume":"158","author":"MA Henning","year":"2010","unstructured":"Henning MA, Kazemi AP (2010) k-tuple total domination in graphs. Discrete Appl Math 158:1006\u20131011","journal-title":"Discrete Appl Math"},{"key":"932_CR20","unstructured":"Jacobson M.S, Peters K (1989) Complexity questions for n-domination and related parameters. In: Eighteenth Manitoba conference on numerical mathematics and computing, Winnipeg, MB, 1988, Congruent Number, vol 68, pp 7\u201322"},{"key":"932_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.09.006","volume":"704","author":"DY Kang","year":"2017","unstructured":"Kang DY, Kwon O-J, Stromme TJF, Telle JA (2017) A width parameter useful for chordal and co-comparability graphs. Theore Comput Sci 704:1\u201317","journal-title":"Theore Comput Sci"},{"issue":"3","key":"932_CR22","doi-asserted-by":"publisher","first-page":"419","DOI":"10.7151\/dmgt.1616","volume":"32","author":"AP Kazemi","year":"2012","unstructured":"Kazemi AP (2012) On the total k-domination number of graphs. Discuss Math Graph Theory 32(3):419\u2013426","journal-title":"Discuss Math Graph Theory"},{"key":"932_CR23","unstructured":"Kulli VR (1991) On n-total domination number in graphs. In: Graph theory, combinatorics, algorithms, and applications, San Francisco, CA, 1989. PA, SIAM, Philadelphia, pp 319\u2013324"},{"issue":"10\u201311","key":"932_CR24","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1016\/j.dam.2013.01.015","volume":"161","author":"JK Lan","year":"2013","unstructured":"Lan JK, Chang GJ (2013) Algorithmic aspects of the k-domination problem in graphs. Discrete Appl Math 161(10\u201311):1513\u20131520","journal-title":"Discrete Appl Math"},{"key":"932_CR25","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.dam.2014.04.007","volume":"174","author":"JK Lan","year":"2014","unstructured":"Lan JK, Chang GJ (2014) On the algorithmic complexity of k-tuple total domination. Discrete Appl Math 174:81\u201391","journal-title":"Discrete Appl Math"},{"issue":"2","key":"932_CR26","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.tcs.2015.03.012","volume":"16","author":"P Li","year":"2015","unstructured":"Li P, Wu Y (2015) Spanning connectedness and Hamiltonian thickness of graphs and interval graphs. Discrete Math Theor Comput Sci 16(2):125\u2013210","journal-title":"Discrete Math Theor Comput Sci"},{"issue":"1","key":"932_CR27","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/140981265","volume":"31","author":"P Li","year":"2017","unstructured":"Li P, Wu Y (2017) A linear time algorithm for the 1-fixed-endpoint path cover problem on interval graphs. SIAM J Discrete Math 31(1):210\u2013239","journal-title":"SIAM J Discrete Math"},{"key":"932_CR28","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0898-1221(93)90308-I","volume":"25","author":"PJ Looges","year":"1993","unstructured":"Looges PJ, Olariu S (1993) Optimal greedy algorithms for indifference graphs. Comput Math Appl 25:15\u201325","journal-title":"Comput Math Appl"},{"key":"932_CR29","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-94-009-5315-4_2","volume-title":"Graphs and Orders","author":"RH M\u00f6hring","year":"1985","unstructured":"M\u00f6hring RH (1985) Algorithmic aspects of comparability graphs and interval graphs. In: Rival I (ed) Graphs and Orders. D. Reidel, Boston, pp 41\u2013101"},{"issue":"21","key":"932_CR30","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1016\/j.ipl.2012.07.010","volume":"112","author":"D Pradhan","year":"2012","unstructured":"Pradhan D (2012) Algorithmic aspects of k-tuple total domination in graphs. Inf Process Lett 112(21):816\u2013822","journal-title":"Inf Process Lett"},{"key":"932_CR31","doi-asserted-by":"crossref","unstructured":"Pramanik T, Mondal S, Pal M, Minimum 2-tuple dominating set of an interval graph. Int J Comb, Volume 2011, Article ID 389369, 14 pages","DOI":"10.1155\/2011\/389369"},{"key":"932_CR32","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0020-0190(88)90091-9","volume":"27","author":"G Ramalingam","year":"1988","unstructured":"Ramalingam G, Rangan CP (1988) A uniform approach to domination problems on interval graphs. Inf Process Lett 27:271\u2013274","journal-title":"Inf Process Lett"},{"key":"932_CR33","first-page":"235","volume":"59","author":"A Raychaudhuri","year":"1987","unstructured":"Raychaudhuri A (1987) On powers of interval and unit interval graphs. Congr Numer 59:235\u2013242","journal-title":"Congr Numer"},{"key":"932_CR34","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2021.01.005","volume":"859","author":"J Shang","year":"2021","unstructured":"Shang J, Li P, Shi Y (2021) The longest cycle problem is polynomial on interval graphs. Theor Comput Sci 859:37\u201347","journal-title":"Theor Comput Sci"},{"key":"932_CR35","first-page":"237","volume-title":"Surveys in combinatorics. London mathematical society lecture note series","author":"WT Trotter","year":"1997","unstructured":"Trotter WT (1997) New perspectives on interval orders and interval graphs. In: Bailey RA (ed) Surveys in combinatorics. London mathematical society lecture note series, vol 241. Cambridge University Press, Cambridge, pp 237\u2013286"},{"key":"932_CR36","doi-asserted-by":"crossref","unstructured":"Yang S, Wang H A note on the 2-tuple total domination problem in Harary graphs. In: 2016 International computer symposium","DOI":"10.1109\/ICS.2016.0022"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00932-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00932-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00932-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,4]],"date-time":"2023-02-04T07:45:37Z","timestamp":1675496737000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00932-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,22]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["932"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00932-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,11,22]]},"assertion":[{"value":"30 October 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"14"}}