几类特殊图中的最小最大多路割

• 作者: 李曙光 辛晓
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 最小最大多路割 链图 环图 树图 限制树宽图
• 年，卷（期）: 2011,（7）
• 所属期刊栏目: 人工智能
• 页码范围: 216-219
• 分类号: TP301
• 字数: 4594字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2011.07.048

摘要

给定边具有正权的无向图,并指定若干个称为终端的顶点,最小最大多路割问题是要得到所有顶点的一个聚类,要求每个子类恰好包含一个终端,并使得所有子类的最大费用最小.子类的费用定义为该子类边界上所有边的权之和.最小最大多路割问题源于对等网络中的数据放置,是传统多路割问题的一个变形.当给定无向图是树图时,这一问题已经是强NP难解的.对于链图和环图,给出了线性时间的精确算法,该算法同时也使得所有子类的总费用最小.对于树图和限制树宽图,给出了(2-1/2k2)-近似算法,k表示终端的数目.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李曙光	山东工商学院计算机科学与技术学院	37	167	7.0	11.0
3	辛晓	山东工商学院外国语学院	3	11	1.0	3.0