Paired domination on interval and circular-arc graphs. (English) Zbl 1124.05070

Summary: We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an \(O(m+n)\) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in \(O(m(m+n))\) time.


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms
Full Text: DOI Link


[1] Bonuccelli, M.A., Dominating sets and domination number of circular-arc graphs, Discrete appl. math., 12, 203-213, (1985) · Zbl 0579.05051
[2] Booth, K.S.; Lueker, G.S., Testing for consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J. comput. syst. sci., 13, 335-379, (1976) · Zbl 0367.68034
[3] Chang, M.S., Efficient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. comput., 27, 1671-1694, (1998) · Zbl 0911.05051
[4] Eschen, E.M.; Spinrad, J.P., An \(\operatorname{O}(n^2)\) algorithm for circular-arc graph recognition, (), 128-137 · Zbl 0801.68128
[5] Golumbic, M.C., Interval graphs and related topics, Discrete math., 55, 113-121, (1985) · Zbl 0568.05046
[6] Haynes, T.W.; Hedetniemi, S.T.; Slater, P.J., Domination in graphs: advanced topics, (1998), Marcel Dekker New York · Zbl 0883.00011
[7] Haynes, T.W.; Slater, T.W., Paired-domination in graphs, Networks, 32, 199-206, (1998) · Zbl 0997.05074
[8] Laskar, R.; Pfaff, J.; Hedetniemi, S.M.; Hedetniemi, S.T., On the algorithmic complexity of total domination, SIAM J. algebraic discrete methods, 5, 420-425, (1984) · Zbl 0576.68056
[9] Qiao, H.; Kang, L.Y.; Cardei, M.; Du, D.Z., Paired-domination of trees, J. global optim., 25, 43-54, (2003) · Zbl 1013.05055
[10] Ramalingan, G.; Rangan, C.P., Total domination in interval graphs revisited, Inform. process. lett., 27, 17-21, (1988) · Zbl 0662.68069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.