{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T18:02:04Z","timestamp":1755799324002},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T00:00:00Z","timestamp":1591401600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T00:00:00Z","timestamp":1591401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s00224-020-09988-3","type":"journal-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T08:02:38Z","timestamp":1591430558000},"page":"1225-1241","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity and Algorithms for Semipaired Domination in Graphs"],"prefix":"10.1007","volume":"64","author":[{"given":"Michael A.","family":"Henning","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arti","family":"Pandey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vikash","family":"Tripathi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"key":"9988_CR1","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation Springer (1999)","DOI":"10.1007\/978-3-642-58412-1"},{"key":"9988_CR2","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Leuker, G.S.: Testing for consecutive ones property, interval graphs, and graph planarity using PQ- tree algorithms. J. Comput. System Sci. 13, 335\u2013379 (1976)","journal-title":"J. Comput. System Sci."},{"key":"9988_CR3","doi-asserted-by":"crossref","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","volume":"206","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of dominating set problems in bounded degree graphs. Inform. and Comput. 206, 1264\u20131275 (2008)","journal-title":"Inform. and Comput."},{"key":"9988_CR4","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the ACM Symposium on Theory of Computing, STOC, pp 624\u2013633. ACM, New York (2014)","DOI":"10.1145\/2591796.2591884"},{"key":"9988_CR5","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific J. Math. 15, 835\u2013855 (1965)","journal-title":"Pacific J. Math."},{"key":"9988_CR6","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2005","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Elsevier Science B.V., Amsterdam (2005)"},{"key":"9988_CR7","volume-title":"Algorithmic Graph Theory and Perfect Graphs, vol. 57","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, vol. 57. Academic Press, New York (1980)"},{"key":"9988_CR8","volume-title":"Fundamentals of Domination in Graphs, vol. 208","author":"TW Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs, vol. 208. Marcel Dekker Inc., New York (1998)"},{"key":"9988_CR9","volume-title":"Domination in Graphs: Advanced Topics, vol. 209","author":"TW Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in Graphs: Advanced Topics, vol. 209. Marcel Dekker Inc., New York (1998)"},{"key":"9988_CR10","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/s10878-018-0303-9","volume":"36","author":"TW Haynes","year":"2018","unstructured":"Haynes, T.W., Henning, M.A.: Perfect graphs involving semitotal and semipaired domination. J.Comb. Optim. 36, 416\u2013433 (2018)","journal-title":"J.Comb. Optim."},{"key":"9988_CR11","first-page":"93","volume":"104","author":"TW Haynes","year":"2018","unstructured":"Haynes, T.W., Henning, M.A.: Semipaired domination in graphs. J. Combin. Math. Combin 104, 93\u2013109 (2018)","journal-title":"J. Combin. Math. Combin"},{"key":"9988_CR12","doi-asserted-by":"crossref","first-page":"659","DOI":"10.7151\/dmgt.2143","volume":"39","author":"TW Haynes","year":"2019","unstructured":"Haynes, T.W., Henning, M.A.: Graphs with large semipaired domination number. Discuss. Math. Graph Theory 39, 659\u2013671 (2019)","journal-title":"Discuss. Math. Graph Theory"},{"key":"9988_CR13","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F","volume":"32","author":"TW Haynes","year":"1998","unstructured":"Haynes, T.W., Slater, P.J.: Paired domination in graphs. Networks 32, 199\u2013206 (1998)","journal-title":"Networks"},{"key":"9988_CR14","doi-asserted-by":"crossref","first-page":"819","DOI":"10.1007\/s00373-018-1916-6","volume":"34","author":"MA Henning","year":"2018","unstructured":"Henning, M.A., Kaemawichanurat, P.: Semipaired domination in claw-free cubic graphs. Graphs Combin. 34, 819\u2013844 (2018)","journal-title":"Graphs Combin."},{"key":"9988_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4614-6525-6","volume-title":"Total Domination in Graphs","author":"MA Henning","year":"2013","unstructured":"Henning, M.A., Yeo, A.: Total Domination in Graphs. Springer, New York (2013)"},{"key":"9988_CR16","doi-asserted-by":"crossref","unstructured":"Henning, M.A., Pandey, A., Tripathi, V: Complexity algorithms for semipaired domination in graphs. In: IWOCA Lecture Notes in Comp. Sci., vol. 11638, pp 278\u2013289 (2019)","DOI":"10.1007\/978-3-030-25005-8_23"},{"key":"9988_CR17","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.ipl.2003.10.004","volume":"89","author":"R Klasing","year":"2004","unstructured":"Klasing, R., Laforest, C.: Hardness results and approximation algorithms of k-tuple domination in graphs. Inform. Process. Lett. 89, 75\u201383 (2004)","journal-title":"Inform. Process. Lett."},{"key":"9988_CR18","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity Springer (2013)","DOI":"10.1007\/978-1-4471-5559-1"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09988-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-09988-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09988-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,5]],"date-time":"2021-06-05T23:16:07Z","timestamp":1622934967000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-09988-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,6]]},"references-count":18,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["9988"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-09988-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,6]]},"assertion":[{"value":"6 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}