The objective of this study is to investigate a network failure problem with a significant path, emerging from the context of crisis management, such as in the case of natural disasters. For a given tree with m failed...The objective of this study is to investigate a network failure problem with a significant path, emerging from the context of crisis management, such as in the case of natural disasters. For a given tree with m failed edges, we assume that we have sufficient resources to recover k edges of the m edges. Each node has a positive weight. In this situation, we consider which k edges should be fixed in order to maximize the sum of the weights of the nodes reachable from the significant path. In this paper, we formulate such a problem as a combinatorial problem. Further, we show that a part of our problem may be solved by translating it into the terms of the so-called tree knapsack problem.展开更多
文摘The objective of this study is to investigate a network failure problem with a significant path, emerging from the context of crisis management, such as in the case of natural disasters. For a given tree with m failed edges, we assume that we have sufficient resources to recover k edges of the m edges. Each node has a positive weight. In this situation, we consider which k edges should be fixed in order to maximize the sum of the weights of the nodes reachable from the significant path. In this paper, we formulate such a problem as a combinatorial problem. Further, we show that a part of our problem may be solved by translating it into the terms of the so-called tree knapsack problem.