| 引用本文: | 张光铎,王正志.图论中独立支配集的最佳求解算法研究.[J].国防科技大学学报,1995,17(2):78-85.[点击复制] |
| Zhang Guangduo,Wang Zhengzhi.An Optimum Solving Algorithm of Independent-Dominating Set in Graph Theory[J].Journal of National University of Defense Technology,1995,17(2):78-85[点击复制] |
|
| |
|
|
| 本文已被：浏览 6347次 下载 1058次 |
| 图论中独立支配集的最佳求解算法研究 |
| 张光铎, 王正志 |
|
(国防科技大学 自动控制系 湖南 长沙 410073)
|
| 摘要: |
| 通过对图论中独立集和支配集的深入研究，提出了独立支配集的概念，论证了独立支配集同极大独立集及极小支配集之间的内在联系，并在此基础上给出了独立支配集的最佳求解算法，从而圆满地解决了图论中独立集及支配集的求解问题，对图的着色及匹配等问题的研究均有相当重要的借鉴意义。 |
| 关键词: 独立集 支配集 独立支配集 |
| DOI： |
| 投稿日期：1994-12-20 |
| 基金项目: |
|
| An Optimum Solving Algorithm of Independent-Dominating Set in Graph Theory |
| Zhang Guangduo, Wang Zhengzhi |
|
(Department of Automatic Control)
|
| Abstract: |
| Through researching into the independent and dominating set in graph theory, this paper has put forward a concept of independent-dominating set and has expounded and proved the internal relationship among the following three concepts: independent-dominating set, maximal independent set and minimal dominating set. On the basis of arranging the vertices set of a given graph in a reasonable sequence，this paper has given out some optimun solving algorithms with a low complexity O(n3)，which has settled satisfactorily and efficiently the solving problem of maximum independent (-dominating) set and minimum (independent-) dominating set in graph theory. The method and the algorithms provided in this paper can certainly be used for reference in studying the problems of graph coloring, covering and matching and so on. |
| Keywords: independent set dominating set independent-dominating set |
|
|
