English

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (2): 103-112.doi: 10.15960/j.cnki.issn.1007-6093.2025.02.008

• 论文 • 上一篇    下一篇

最小分枝支撑树问题及其在选址问题中的应用

林浩1,*(), 何程1   

  1. 1. 河南工业大学数学与统计学院, 河南郑州 450001
  • 收稿日期:2022-04-18 出版日期:2025-06-15 发布日期:2025-06-12
  • 通讯作者: 林浩 E-mail:linhao@haut.edu.cn
  • 基金资助:
    河南省高校重点研究项目(20A110003)

Minimum branch spanning tree problem and its applications to the location problems

Hao LIN1,*(), Cheng HE1   

  1. 1. School of Mathematics and Statistics, Henan University of Technology, Zhengzhou 450001, Henan, China
  • Received:2022-04-18 Online:2025-06-15 Published:2025-06-12
  • Contact: Hao LIN E-mail:linhao@haut.edu.cn

RichHTML

0

PDF

43

摘要：

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

关键词: 支撑树最优化, 形心分枝, 选址问题, NP-困难性

Abstract:

For a spanning tree T of graph G, the centroid of T is a vertex v for which the largest component of $T-v$ has as few vertices as possible. The number of vertices of this component is called the centroid branch weight of T. The minimum branch spanning tree problem is to find a spanning tree T of G such that the centroid branch weight is minimized. This minimum value is called the branch index of G. In application to design of communication networks, the loads of all branches leading from the switch center (centroid) should be as balanced as possible. In 2022, we proposed this new type of location problem and presented basic theoretic results. This paper is devoted to deepen the study on theory and algorithms. We first prove that the weighted version of the problem is NP-hard even for planar graphs. Then, we determine the exact formulas of branch indices for several important graph families, such as polyhedral graphs, hypercubes, and graph product $K_m\times K_n$, co-bipartite graphs, and establish a heuristic algorithm.

Key words: spanning tree optimization, centroid branch, location problem, NP-hard

中图分类号: