The Partial Inverse Minimum Connected Spanning Subgraph Problem with Given Cyclomatic Number

摘要：

　　In this paper,we consider a partial inverse problem of minimum connected spanning subgraph with cyclomatic number k.That is,given a subgraph,a cyclomatic number k and a constraint that the edge weights can only decrease,we want to modify the edge weights as little as possible,so that there exists a minimum connected spanning subgraph with cyclomatic number k and containing the given subgraph.For the case that the given subgraph is a connected subgraph with cyclomatic number k,we solve the problem in polynomial time by contracting the subgraph.And when the given subgraph is a spanning tree,we solve the problem in polynomial time by using the MST algorithm.

关键词： Cyclomatic number minimum connected spanning subgraph MST algorithm partial inverse problem

作者: Zheheng Ding Fang Zhu Qin Wang

作者单位: Department of Mathematics,China Jiliang University,Hangzhou 310018,China

会议类型: 国际会议

会议名称: 2013 2nd international Conference on Opto-Electronics Engineering and Materials Eesearch(2013第二届光电工程与材料研究国际会议)(OEMR2013)

会议地点: 郑州

会议语种:英文

页码: 2105-2109

在线出版日期: 2013-10-19（万方平台首次上网日期，不代表论文的发表时间）