並列摘要
Roman domination in a graph G refers to an assignment of labels 0, 1, or 2 to each vertex. Vertices labeled 0 must have at least one neighbor labeled 2. The weight of a Roman domination is the sum of all vertex labels. A circular-arc graph G is defined by a set F of arcs on a circle, where each arc corresponds to a vertex in G. Vertices v and u are adjacent if and only if their corresponding arcs intersect on the circle. The Roman domination problem seeks a Roman domination function with the minimum total weight across all possible assignments. In previous research, an O(n^2) algorithm was proposed to solve the Roman Domination Problem on circular-arc graphs. The objective of this thesis is to develop a linear-time algorithm to efficiently address the Roman Domination Problem on circular-arc graphs.
參考文獻
S. Arnborg and A. Proskurowski. Linear time algorithms for np-hard problems re stricted to partial k-trees. Discrete applied mathematics, 23(1):11–24, 1989.
H. Balakrishnan, A. Rajaraman, and C. P. Rangan. Connected domination and steiner set on asteroidal triple-free graphs. In Algorithms and Data Structures: Third Workshop, WADS’93 Montréal, Canada, August 11–13, 1993 Proceedings 3, pages 131–141. Springer, 1993.
M.-S. Chang. Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM Journal on computing, 27(6):1671–1694, 1998.
L. Chen, C. Lu, and Z. Zeng. A linear-time algorithm for paired-domination problem in strongly chordal graphs. Information processing letters, 110(1):20–23, 2009.
L. Chen, C. Lu, and Z. Zeng. Labelling algorithms for paired-domination problems in block and interval graphs. Journal of combinatorial optimization, 19(4):457–470, 2010.