Home

Mixed Connected d-Dominating Set Problem
2018-05-03 00:00:00

报告题目:

Mixed Connected d-Dominating Set Problem

报 告 人:

胡捷(武大数学与统计学院)

报告时间:

2018年05月03日 12:15--12:50

报告地点:

理学院东北楼一楼报告厅(110)

报告摘要:

Serving as a virtual backbone for wireless ad hoc networks, the connected

dominating set problem has been widely studied. We design a robust and

survivable connected dominating set for a virtual backbone of a larger graph for

ad hoc network. More specifically, we study the (k; l)-connected d-dominating

set problem. Given a graph G = (V;E), a subset D V is a (k; l)-connected ddominating

set if the subgraph induced by D has mixed connectivity at least (k; l)

and every vertex outside of S has at least d neighbors from D. The type of virtual

backbone is survivable and also robust for sending message under certain number

of both node and link failures.We study the properties of such dominating set and

also IP formulations. In addition, we design a cutting plane algorithm to solve it.