{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T09:43:18Z","timestamp":1791279798232,"version":"4.1.0"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>This paper first presents a unified approach to design efficient algorithms for the weighted domination problem and its three variants, i.e., the weighted independent, connected, and total domination problems, on interval graphs. Given an interval model with endpoints sorted, these algorithms run in time O(n) or O(n log log n) where n is the number of vertices. The results are then extended to solve the same problems on circular-arc graphs in O(n + m) time where m is the number of edges of the input graph.<\/jats:p>","DOI":"10.1137\/s0097539792238431","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1671-1694","source":"Crossref","is-referenced-by-count":83,"title":["Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs"],"prefix":"10.1137","volume":"27","author":[{"given":"Maw-Shang","family":"Chang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"A. Aho, D\u017e. Hopkroft, D\u017e. Ul\u2019man, Postroenie i analiz vychislitelnykh algoritmov, \u201cMir\u201d, 1979, 536\u20130, Translated by A. O. Slisenko; Edited by Ju. V. Matijasevi\u010d80g:68036"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Takao Asano, Dynamic programming on intervals, Lecture Notes in Comput. Sci., Vol. 557, Springer, Berlin, 1991, 199\u201320794f:90053","DOI":"10.1007\/3-540-54945-5_63"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90112-2"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90068-0"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0401032"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90209-G"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190030306"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90025-3"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"R11","unstructured":"M. S. Chang, P. Nagavamsi, and C. Pandu Rangan,\n                      Weighted irredundancy in circular\u2010arc graphs\n                      , manuscript, 1995."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230070305"},{"key":"R13","unstructured":"Elaine Eschen, Jeremy Spinrad, An O(n2) algorithm for circular\u2010arc graph recognition, ACM, New York, 1993, 128\u201313793k:05168"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90061-1"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90014-5"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116878"},{"key":"R17","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040407"},{"key":"R19","volume-title":"Algorithmic graph theory and perfect graphs","author":"Golumbic Martin","year":"1980"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90039-1"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90023-5"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120410"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793260726"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Wen Hsu, Tze Ma, Substitution decomposition on chordal graphs and applications, Lecture Notes in Comput. Sci., Vol. 557, Springer, Berlin, 1991, 52\u20136094d:05131","DOI":"10.1007\/3-540-54945-5_49"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90165-E"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0218005"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/0605040"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90224-J"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1137\/0217003"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90076-2"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90091-9"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90163-R"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90195-6"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/0221061"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"Klaus Simon, A new simple linear algorithm to recognize interval graphs, Lecture Notes in Comput. Sci., Vol. 553, Springer, Berlin, 1991, 289\u201330894g:05086","DOI":"10.1007\/3-540-54891-2_22"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90244-P"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/0209001"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90267-D"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539792238431","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:18Z","timestamp":1787336058000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539792238431"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":40,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539792238431"],"URL":"https:\/\/doi.org\/10.1137\/s0097539792238431","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}