{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T13:31:26Z","timestamp":1745933486953},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2012,9]]},"abstract":"<jats:p> In this paper, we consider minimum total domination problem along with two of its variations namely, minimum signed total domination problem and minimum minus total domination problem for chordal bipartite graphs. In the minimum total domination problem, the objective is to find a smallest size subset TD \u2286 V of a given graph G = (V, E) such that |TD\u2229N<jats:sub>G<\/jats:sub>(v)| \u2265 1 for every v \u2208 V. In the minimum signed (minus) total domination problem for a graph G = (V, E), it is required to find a function f : V \u2192 {-1, 1} ({-1, 0, 1}) such that f(N<jats:sub>G<\/jats:sub>(v)) = \u2211<jats:sub>u\u2208N<jats:sub>G<\/jats:sub>(v)<\/jats:sub>f(u) \u2265 1 for each v \u2208 V, and the cost f(V) = \u2211<jats:sub>v\u2208V<\/jats:sub> f(v) is minimized. We first show that for a given chordal bipartite graph G = (V, E) with a weak elimination ordering, a minimum total dominating set can be computed in O(n + m) time, where n = |V| and m = |E|. This improves the complexity of the minimum total domination problem for chordal bipartite graphs from O(n<jats:sup>2<\/jats:sup>) time to O(n + m) time. We then adopt a unified approach to solve the minimum signed (minus) total domination problem for chordal bipartite graphs in O(n + m) time. The method is also able to solve the minimum k-tuple total domination problem for chordal bipartite graphs in O(n + m) time. For a fixed integer k \u2265 1 and a graph G = (V, E), the minimum k-tuple total domination problem is to find a smallest subset TD<jats:sub>k<\/jats:sub> \u2286 V such that |TD<jats:sub>k<\/jats:sub> \u2229 N<jats:sub>G<\/jats:sub>(v)| \u2265 k for every v \u2208 V. <\/jats:p>","DOI":"10.1142\/s1793830912500450","type":"journal-article","created":{"date-parts":[[2012,8,6]],"date-time":"2012-08-06T08:31:23Z","timestamp":1344241883000},"page":"1250045","source":"Crossref","is-referenced-by-count":19,"title":["COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS"],"prefix":"10.1142","volume":"04","author":[{"given":"D.","family":"PRADHAN","sequence":"first","affiliation":[{"name":"Department of Computer Science and Automation, Indian Institute of Science, Bangalore-560012, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,8,6]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90023-P"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193253415"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90147-P"},{"key":"rf5","first-page":"173","volume":"7","author":"Farber M.","journal-title":"Discrete Appl. Math."},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190020209"},{"key":"rf8","first-page":"143","volume":"29","author":"Harris L.","journal-title":"Australas. J. Combin."},{"key":"rf9","series-title":"Monographs and Textbooks in Pure and Applied Mathematics","volume-title":"Fundamentals of Domination in Graphs","volume":"208","author":"Haynes T. W.","year":"1998"},{"key":"rf10","series-title":"Monographs and Textbooks in Pure and Applied Mathematics","volume-title":"Domination in Graphs: Advanced Topics","volume":"209","author":"Haynes T. W.","year":"1998"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.044"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2003.06.002"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.01.009"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.03.004"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.08.002"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1137\/0216062"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.06.015"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.04.005"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90209-R"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_85"},{"key":"rf22","first-page":"383","volume":"91","author":"Wang H.","journal-title":"Ars Combin."},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.11.011"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013782511179"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830912500450","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:43:47Z","timestamp":1565131427000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830912500450"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,6]]},"references-count":22,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,8,6]]},"published-print":{"date-parts":[[2012,9]]}},"alternative-id":["10.1142\/S1793830912500450"],"URL":"https:\/\/doi.org\/10.1142\/s1793830912500450","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,6]]}}}