树的两类m—路中心 |
| |
引用本文: | 蔡延光,罗狄隐.树的两类m—路中心[J].湖北汽车工业学院学报,1992(1):27-34. |
| |
作者姓名: | 蔡延光 罗狄隐 |
| |
摘 要: | 本文提出图的顶点和边不相交的k—支配路数的概念。并就树的情形对项点和边不相交的k—支配路数分别给出O(n~2logn)算法。从而解决了树的项点和边不相交的m—路中心问题。本文还解决了2]中的一个未决问题。
|
关 键 词: | 算法 支配集 路中心 计算复杂性 |
Two Kinds of m-Path-Centers for Trees |
| |
Abstract: | The concept of m-path-center of a graph is presented . Several algorithms are given to compute the vertex-disjoint and edge-disjoint k-domination-path number of a tree. Therefore we can derive the vertex-disjoint and edge-disjoint m - path - center of a tree in O(n2logn) time. This paper also solves one open problem presented in 2]. |
| |
Keywords: | algorithm dominating set path-center computing complexity location |
本文献已被 维普 等数据库收录! |