Partial Inverse Most Unbalanced Spanning Tree Problem
Partial Inverse Most Unbalanced Spanning Tree Problem
复制标题
部分逆最不平衡生成树问题
作者：
Qin Wang
本文考虑部分逆最不平衡生成树问题，即如何以最小代价修改简单无向赋权图的边权，使部分给定的森林包含在一棵新的最不平衡生成树中。研究了两个模型：加权Hamming距离下的问题和加权L1范数下的问题。我们给出了它们各自的算法，它们都运行在强多项式时间内。斯特雷兹泽尼。Rozwazano cześciowo odwotny njbardziej niezrownowazones问题drzewa rozpinającego，czyli jak modyfikowac wagi brzegow niebezpośrednio wazonego grafu.Rozpatrzono dwa Modele：wazonego dystsu Hamminga I wazonej Normy I1.(Cześciowo odwrotny Najbardziej niezrownowazony Problem drzewa rozpinającego)
In this paper, we consider the partial inverse most unbalanced spanning tree problem, which is how to modify the weights of the edges in a simple undirected weighted graph with minimum cost such that the partially given forest is contained in a new most unbalanced spanning tree. Two models are studied: the problem under the weighted Hamming distance and the problem under the weighted l1 norm. We present their respective algorithms that all run in strongly polynomial times. Streszczenie. Rozwazano cześciowo odwrotny najbardziej niezrownowazony problem drzewa rozpinającego, czyli jak modyfikowac wagi brzegow niebezpośrednio wazonego grafu. Rozpatrzono dwa modele: wazonego dystansu Hamminga i wazonej normy I1. (Cześciowo odwrotny najbardziej niezrownowazony problem drzewa rozpinającego)
登录
查看更多内容
影响因子：
2.9
作者：
Abraham P. Punnen;K. Nair
通讯作者：
Abraham P. Punnen;K. Nair
DOI：
10.1016/j.orl.2005.12.003
发表时间：
2007
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
Xiaoguang Yang;Jianzhon Zhang
通讯作者：
Xiaoguang Yang;Jianzhon Zhang
DOI：
10.1016/j.orl.2007.03.006
发表时间：
2008
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
Qin Wang;Jinjiang Yuan;Jianzhon Zhang
通讯作者：
Qin Wang;Jinjiang Yuan;Jianzhon Zhang
DOI：
10.1016/0166-218x(86)90041-7
发表时间：
1986-11
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
P. Camerini;F. Maffioli;S. Martello;P. Toth
通讯作者：
P. Camerini;F. Maffioli;S. Martello;P. Toth
影响因子：
2.2
作者：
Xiaoguang Yang;Jianzhon Zhang
通讯作者：
Xiaoguang Yang;Jianzhon Zhang