科研之友
微信
新浪微博
Facebook
分享链接
摘要
对图G的支撑树T,其形心是指这样的顶点v,使得T-v的最大分枝具有尽可能少的顶点,这个分枝的顶点数称为T的形心分枝度量。最小分枝支撑树问题是寻求G的支撑树T,使得T的形心分枝度量为最小,这个最小值称为图G的分枝指数。在通信网络设计中,其实际意义是使从交换中心(形心)引出的所有分枝的负荷尽可能均衡。我们在2022年提出这种新型的选址问题,并给出基本的理论结果。本文将加深对理论与算法的研究。首先证明此问题的加权形式即使对平面图也是NP-困难的。然后对一些重要的特殊图类,如多面体图、超立方体、乘积图Km×Kn和二部图的补图等,分别给出这些图类分枝指数的精确值,并得到一个启发式算法。
- 单位
