{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T04:51:40Z","timestamp":1648961500288},"reference-count":28,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:p> In a graph [Formula: see text], the degree of a vertex [Formula: see text], denoted by [Formula: see text], is defined as the number of edges incident on [Formula: see text]. A set [Formula: see text] of vertices of [Formula: see text] is called a strong dominating set if for every [Formula: see text], there exists a vertex [Formula: see text] such that [Formula: see text] and [Formula: see text]. For a given graph [Formula: see text], Min-Strong-DS is the problem of finding a strong dominating set of minimum cardinality. The decision version of Min-Strong-DS is shown to be NP -complete for chordal graphs. In this paper, we present polynomial time algorithms for computing a strong dominating set in block graphs and proper interval graphs, two subclasses of chordal graphs. On the other hand, we show that for a graph [Formula: see text] with [Formula: see text]-vertices, Min-Strong-DS cannot be approximated within a factor of [Formula: see text] for every [Formula: see text], unless NP [Formula: see text] DTIME ([Formula: see text]). We also show that Min-Strong-DS is APX -complete for graphs with maximum degree [Formula: see text]. On the positive side, we show that Min-Strong-DS can be approximated within a factor of [Formula: see text] for graphs with maximum degree [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s1793830919500630","type":"journal-article","created":{"date-parts":[[2019,9,2]],"date-time":"2019-09-02T07:25:16Z","timestamp":1567409116000},"page":"1950063","source":"Crossref","is-referenced-by-count":0,"title":["The strong domination problem in block graphs and proper interval graphs"],"prefix":"10.1142","volume":"11","author":[{"given":"Saikat","family":"Pal","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computing, Indian Institute of Technology (ISM), Dhanbad, Jharkhand 826004, India"}]},{"given":"D.","family":"Pradhan","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computing, Indian Institute of Technology (ISM), Dhanbad, Jharkhand 826004, India"}]}],"member":"219","published-online":{"date-parts":[[2019,12,19]]},"reference":[{"key":"S1793830919500630BIB001","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1974"},{"key":"S1793830919500630BIB002","first-page":"111","volume":"4","author":"Akhbari M. H.","year":"2016","journal-title":"Electronic J. Graph Theory and Appl."},{"key":"S1793830919500630BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62592-5_80"},{"key":"S1793830919500630BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1"},{"key":"S1793830919500630BIB005","doi-asserted-by":"publisher","DOI":"10.1137\/0211015"},{"key":"S1793830919500630BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/0605034"},{"key":"S1793830919500630BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.08.010"},{"key":"S1793830919500630BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.07.003"},{"key":"S1793830919500630BIB009","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"S1793830919500630BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(75)90011-3"},{"key":"S1793830919500630BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00257-1"},{"key":"S1793830919500630BIB012","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"S1793830919500630BIB013","first-page":"73","volume":"26","author":"Hattingh J. H.","year":"1998","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"S1793830919500630BIB014","volume-title":"Domination in Graphs: Advanced Topics","author":"Haynes T. W.","year":"1998"},{"key":"S1793830919500630BIB015","volume-title":"Fundamentals of Domination in Graphs","author":"Haynes T. W.","year":"1998"},{"key":"S1793830919500630BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90089-2"},{"key":"S1793830919500630BIB017","first-page":"192","volume-title":"Combinatorics and Applications","author":"Jamison R. E.","year":"1982"},{"key":"S1793830919500630BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.11.035"},{"key":"S1793830919500630BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.01.015"},{"key":"S1793830919500630BIB020","doi-asserted-by":"publisher","DOI":"10.1137\/0605040"},{"key":"S1793830919500630BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00298-9"},{"key":"S1793830919500630BIB022","first-page":"53","volume":"65","author":"Rad N. J.","year":"2016","journal-title":"Aust. J. Comb."},{"key":"S1793830919500630BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00271-4"},{"key":"S1793830919500630BIB024","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00248-4"},{"key":"S1793830919500630BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00116-3"},{"key":"S1793830919500630BIB026","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00231-K"},{"key":"S1793830919500630BIB028","doi-asserted-by":"publisher","DOI":"10.1137\/0138030"},{"key":"S1793830919500630BIB029","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.01.029"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830919500630","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T06:43:53Z","timestamp":1576824233000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830919500630"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":28,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["10.1142\/S1793830919500630"],"URL":"https:\/\/doi.org\/10.1142\/s1793830919500630","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12]]}}}