TY - JOUR
T1 - Robustness of minimum cost arborescences
AU - Kamiyama, Naoyuki
N1 - Funding Information:
Preliminary version of this paper has appeared in Proceedings of 22nd International Symposium on Algorithms and Computation (ISAAC’11), Lecture Notes in Computer Science 7074 (2011) pp.130–139. Partly supported by a Grant-in-Aid for Scientific Research (22700016) from Japan Society for the Promotion of Science.
PY - 2012/10
Y1 - 2012/10
N2 - The minimum cost arborescence problem is a directed graph analogue of theminimum spanning tree problem in an undirected graph. In this paper, we study the minimum cost arborescence problem from the viewpoint of robustness of the optimal objective value, and we characterize an input graph in which the optimal objective value does not change even if we remove several arcs.
AB - The minimum cost arborescence problem is a directed graph analogue of theminimum spanning tree problem in an undirected graph. In this paper, we study the minimum cost arborescence problem from the viewpoint of robustness of the optimal objective value, and we characterize an input graph in which the optimal objective value does not change even if we remove several arcs.
UR - http://www.scopus.com/inward/record.url?scp=84870900513&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84870900513&partnerID=8YFLogxK
U2 - 10.1007/s13160-012-0079-8
DO - 10.1007/s13160-012-0079-8
M3 - Article
AN - SCOPUS:84870900513
SN - 0916-7005
VL - 29
SP - 485
EP - 497
JO - Japan Journal of Industrial and Applied Mathematics
JF - Japan Journal of Industrial and Applied Mathematics
IS - 3
ER -