排列圖上的羅馬支配問題

Roman Domination Problem on Permutation Graphs

葉庭熙(Ting-Hsi Yeh)

指導教授 ： 唐傳義

國立清華大學/電機資訊學院/資訊工程學系/碩士(2007年)

https://doi.org/10.6843/NTHU.2007.00617

摘要

無資料

關鍵字

羅馬支配問題 ； 排列圖 ； 支配點集合 ； 演算法 ； 有序支配對

並列摘要

無資料

並列關鍵字

roman domination problem ； permutation graph ； dominating set ； algorithm ； order cross pair

參考文獻

[2] I. Stewart, Defend the Roman Empire, Scientific American 281 (1999) 136-139.

[5] M. Liedloff, T. Kloks, J. Liu, and S.-L. Peng, Roman domination over some

[6] H.S. Chao, F.R. Hsu, R.C.T. Lee, An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs, Discrete Applied Mathematics 102 (2000) 159-173

[7] C.S. ReVelle, K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (7) (2000) 585–594.

[8]M.C. Golumbic, Algorithm Graph Teory and Perfect Graphs (Academic Press, New York, 1980).