Citation: | X. Chen, C. Tang, Z. Zhang, and G. Chen, “A game-theoretic approach to solving the Roman domination problem,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 0, pp. 1–17, Aug. 2023. doi: 10.1109/JAS.2023.123840 |
[1] |
I. Stewart, “Defend the Roman Empire!” Scientific American, vol. 281, no. 6, pp. 136–138, Dec. 1999.
|
[2] |
E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi, and S. T. Hedetniemi, “Roman domination in graphs,” Discrete Mathematics, vol. 278, no. 1, pp. 11–22, 2004.
|
[3] |
A. Pagourtzis, P. Penna, K. Schlude, K. Steinhöfel, D. S. Taylor, and P. Widmayer, Server Placements, Roman Domination and Other Dominating Set Variants. Boston, MA: Springer US, 2002, pp. 280–291.
|
[4] |
F. Ghaffari, B. Bahrak, and S. P. Shariatpanahi, “A novel approach to partial coverage in wireless sensor networks via the Roman dominating set,” IET Networks, vol. 11, no. 2, pp. 58–69, 2022. doi: 10.1049/ntw2.12034
|
[5] |
C. S. ReVelle and K. E. Rosing, “Defendens imperium romanum: A classical problem in military strategy,” The American Mathematical Monthly, vol. 107, no. 7, pp. 585–594, 2000. doi: 10.1080/00029890.2000.12005243
|
[6] |
P. A. Dreyer, “Applications and variations of domination in graphs,” 2000.
|
[7] |
W. Shang and X. Hu, “The Roman domination problem in unit disk graphs,” in Computational Science. Springer Berlin Heidelberg, 2007, pp. 305–312.
|
[8] |
L. Wang, Y. Shi, Z. Zhang, Z.-B. Zhang, and X. Zhang, “Approximation algorithm for a generalized Roman domination problem in unit ball graphs,” J. Combinatorial Optimization, vol. 39, no. 1, pp. 138–148, 2020. doi: 10.1007/s10878-019-00459-1
|
[9] |
H. A. Abdollahzadeh, A. M. Henning, V. Samodivkin, and G. I. Yero, “Total Roman domination in graphs,” Applicable Analysis and Discrete Mathematics, vol. 10, pp. 501–517, 2016. doi: 10.2298/AADM160802017A
|
[10] |
A. Ghaffari-Hadigheh, “Roman domination problem with uncertain positioning and deployment costs,” Soft Computing, vol. 24, no. 4, pp. 2637–2645, 2020. doi: 10.1007/s00500-019-03811-z
|
[11] |
M. Hajjari, H. A. Ahangar, R. Khoeilar, Z. Shao, and S. M. Sheikholeslami, “New bounds on the triplE Roman domination number of graphs,” J. Mathematics, vol. 2022, pp. 1–5, 2022.
|
[12] |
X. Chen, G. Hao, and Z. Xie, “A note on Roman domination of digraphs,” Discussiones Mathematicae Graph Theory, vol. 39, no. 1, pp. 13–21, 2019. doi: 10.7151/dmgt.2067
|
[13] |
L. Ouldrabah, M. Blidia, and A. Bouchou, “Roman domination in oriented trees,” Electronic J. Graph Theory and Applications, vol. 9, no. 1, pp. 95–103, 2021. doi: 10.5614/ejgta.2021.9.1.9
|
[14] |
P. Pavlič and J. Žerovnik, “Roman domination number of the cartesian products of paths and cycles,” The Electronic J. Combinatorics, vol. 19, no. 3, pp. 19–56, 2012. doi: 10.37236/2595
|
[15] |
M. Reddappa and D. C. J. S. Reddy, “Total Roman domination in special type interval graph,” Int. J. Engineering Research &Technology, vol. 8, no. 10, pp. 343–348, 2019.
|
[16] |
E. Cockayne, P. Grobler, W. Gründlingh, J. Munganga, and J. Vuuren, “Protection of a graph,” Utilitas Mathematica, vol. 67, pp. 19–32, 2005.
|
[17] |
H. Peters, Game Theory, a Multi-Leveled Approach, 2nd ed. Berlin, Heidelberg: Springer-Verlag, 2008.
|
[18] |
L.-H. Yen and Z.-L. Chen, “Game-theoretic approach to self-stabilizing distributed formation of minimal multi-dominating sets,” IEEE Trans. Parallel and Distributed Systems, vol. 25, no. 12, pp. 3201–3210, 2014. doi: 10.1109/TPDS.2013.2297100
|
[19] |
L.-H. Yen and G.-H. Sun, “Game-theoretic approach to self-stabilizing minimal independent dominating sets,” in Internet and Distributed Computing Systems, Cham, 2018, pp. 173–184.
|
[20] |
X. Chen and Z. Zhang, “A game theoretic approach for minimal connected dominating set,” Theoretical Computer Science, vol. 836, pp. 29–36, 2020. doi: 10.1016/j.tcs.2020.05.020
|
[21] |
X. Chen, C. Tang, and Z. Zhang, “A game theoretic approach for minimal secure dominating set,” To appear in IEEE/CAA J. Automatica Sinica.
|
[22] |
Y. Yang and X. Li, “Towards a snowdrift game optimization to vertex cover of networks,” IEEE Trans. Cybernetics, vol. 43, no. 3, pp. 948–956, 2013. doi: 10.1109/TSMCB.2012.2218805
|
[23] |
C. Tang, A. Li, and X. Li, “Asymmetric game: A silver bullet to weighted vertex cover of networks,” IEEE Trans. Cybernetics, vol. 48, no. 10, pp. 2994–3005, 2018. doi: 10.1109/TCYB.2017.2754919
|
[24] |
C. Sun, W. Sun, X. Wang, and Q. Zhou, “Potential game theoretic learning for the minimal weighted vertex cover in distributed networking systems,” IEEE Trans. Cybernetics, vol. 49, no. 5, pp. 1968–1978, 2019. doi: 10.1109/TCYB.2018.2817631
|
[25] |
C. Sun, H. Qiu, W. Sun, Q. Chen, L. Su, X. Wang, and Q. Zhou, “Better approximation for distributed weighted vertex cover via game-theoretic learning,” IEEE Trans. Systems,Man,and Cybernetics: Systems, vol. 52, no. 8, pp. 5308–5319, 2022. doi: 10.1109/TSMC.2021.3121695
|
[26] |
C. Sun, X. Wang, H. Qiu, and Q. Chen, “A game theoretic solver for the minimum weighted vertex cover,” in Proc. 2019 IEEE Int. Conf. Systems, Man and Cybernetics, 2019, pp. 1920–1925.
|
[27] |
J. Chen, K. Luo, C. Tang, Z. Zhang, and X. Li, “Optimizing polynomial-time solutions to a network weighted vertex cover game,” IEEE/CAA J. Autom. Sinica, pp. 1–12, 2022.
|
[28] |
X.-Y. Li, Z. Sun, W. Wang, X. Chu, S. Tang, and P. Xu, “Mechanism design for set cover games with selfish element agents,” Theoretical Computer Science, vol. 411, no. 1, pp. 174–187, 2010. doi: 10.1016/j.tcs.2009.09.024
|
[29] |
X.-Y. Li, Z. Sun, W. Wang, and W. Lou, “Cost sharing and strategyproof mechanisms for set cover games,” J. Comb. Optim., vol. 20, pp. 259–284, 2010. doi: 10.1007/s10878-009-9209-x
|
[30] |
Q. Fang and L. Kong, “Core stability of vertex cover games,” in Internet and Network Economics. Springer Berlin Heidelberg, 2007, pp. 482–490.
|
[31] |
B. van Velzen, “Dominating set games,” Operations Research Letters, vol. 32, no. 6, pp. 565–573, 2004. doi: 10.1016/j.orl.2004.02.004
|
[32] |
H. K. Kim, “On connected dominating set games,” J. the Korean Data and Information Science Society, vol. 22, pp. 1275–1281, 2011.
|
[33] |
X. Ai, V. Srinivasan, and C. Tham, “Optimality and complexity of pure Nash equilibria in the coverage game,” IEEE J. Selected Areas in Communications, vol. 26, no. 7, pp. 1170–1182, 2008. doi: 10.1109/JSAC.2008.080914
|
[34] |
J. F. Nash, “Equilibrium points in n-person games,” Proc. the National Academy of Sciences, vol. 36, no. 1, pp. 48–49, 1950. doi: 10.1073/pnas.36.1.48
|
[35] |
C. Padamutham and V. S. R. Palagiri, “Algorithmic aspects of Roman domination in graphs,” J. Applied Mathematics and Computing, vol. 64, no. 1, pp. 89–102, 2020.
|
[36] |
D. Monderer and L. Shapley, “Potential games,” Games and Economic Behavior, vol. 14, pp. 124–143, 1996. doi: 10.1006/game.1996.0044
|
[37] |
A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. doi: 10.1126/science.286.5439.509
|
[38] |
P. Erdös and A. Rényi, “On random graphs l,” Publicationes Mathematicae Debrecen, vol. 6, pp. 290–297, 1959.
|
[39] |
K. Li, Y. Ran, Z. Zhang, and D.-Z. Du, “Nearly tight approximation algorithm for (connected) Roman dominating set,” Optimization Letters, vol. 16, no. 8, pp. 2261–2276, 2022. doi: 10.1007/s11590-022-01862-0
|
[40] |
Y. Li and A. S. Morse, “The power allocation game on a network: A paradox,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 4, pp. 771–776, 2018. doi: 10.1109/JAS.2018.7511129
|
[41] |
G. Zhao, Y. Wang, and H. Li, “A matrix approach to the modeling and analysis of networked evolutionary games with time delays,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 4, pp. 818–826, 2018. doi: 10.1109/JAS.2016.7510259
|
[42] |
D. Cheng, T. Xu, F. He, and H. Qi, “On dynamics and Nash equilibriums of networked games,” IEEE/CAA J. Autom. Sinica, vol. 1, no. 1, pp. 10–18, 2014. doi: 10.1109/JAS.2014.7004614
|
[43] |
M. Ye, D. Li, Q.-L. Han, and L. Ding, “Distributed Nash equilibrium seeking for general networked games with bounded disturbances,” IEEE/CAA J. Autom. Sinica, pp. 1–12, 2022.
|
[44] |
T. Roughgarden, “The price of anarchy is independent of the network topology,” J. Computer and System Sciences, vol. 67, no. 2, pp. 341–364, 2003. doi: 10.1016/S0022-0000(03)00044-8
|
[45] |
M. J. Osborne and A. Rubinstein, A Course in Game Theory, 1st ed. London, England: MIT Press, 1994.
|