Approximation algorithms for set cover problems with graph structures

图结构集合覆盖问题的近似算法

• 批准号: 25330026
• 负责人: ZHAO LIANG
• 金额: $ 2.91万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2013
• 资助国家: 日本
• 起止时间: 2013-04-01 至 2017-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-25330026/
• 关键词: 支配集合; 集合被覆; distance dominating; network algorithm; democratic number; outerplanar graph; 一票の格差; Dominating set; distacne dominating; set cover; distance covering

项目成果

$gamma_k(G) le lfloor frac{n}{2k+1} rfloor$ for maximal outerplanar graphs satisfying $n bmod (2k+1) le 4$

$gamma_k(G) le lfloor frac{n}{2k 1} rfloor$ 用于满足 $n bmod (2k 1) le 4$ 的最大外平面图

• 发表时间: 2014
• 期刊: Proc. of the 17th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2014)
• 作者: Liang Zhao;Jia Li and Dorothea Wagner
• 通讯作者: Jia Li and Dorothea Wagner

A Practical Approach for Finding Small {Independent, Distance} Dominating Sets in Large-Scale Graphs

在大规模图中查找小{独立，距离}支配集的实用方法

• DOI: 10.1007/978-3-319-03889-6_18
• 发表时间: 2013
• 期刊: Lecture Notes in Computer Science
• 作者: Liang Zhao;Hiroshi Kadowaki;Dorothea Wagner
• 通讯作者: Dorothea Wagner

"Finding Small Dominating Sets in Large-Scale Networks," in Big Data of Complex Networks

复杂网络大数据中的“在大规模网络中寻找小型支配集”

• 发表时间: 2016
• 作者: X. Hua;N. Yamashita;永田裕一，今堀慎治;趙 亮;永田裕一，今堀慎治;Liang Zhao
• 通讯作者: Liang Zhao

民主度指数を用いた代表選と一票格差への考察

使用民主指数考虑代表选举和​​选票差距

• 发表时间: 2016
• 作者: Liang Zhao;Hiroshi Kadowaki;Dorothea Wagner;山下信雄;Liang Zhao;山川雄也，山下信雄;趙 亮
• 通讯作者: 趙 亮

大連理工大学(中国)

大连理工大学（中国）