首页 | 本学科首页   官方微博 | 高级检索  
     检索      

树的两类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
本文献已被 维普 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号