Minimise pruning cost of a node-weighted directed acyclic graph on applications of management. (4th July 2022) - Chen, Zhi-Ming; Lee, Cheng-Hsiung; Lin, Yu-Feng
A novel optimisation problem is proposed in this research. In the proposed model, a corporation is represented as a directed acyclic graph (DAG) with weight. A directed edge in the DAG represents the relationship between a division and its subdivision. The weight denotes the pruning cost of each node. The objective is to partition the graph into two parts so that one of the parts would be pruned to minimise total pruning cost. The proposed model can be formulated as an integer linear programming problem which is hard to find the optimal solution. In this research, we show that it can be solved in polynomial time by using a general linear programming solver. Furthermore, we propose an improvement method which the optimal solution can be solved much more quickly than only using a general LP solver.