CAJ | 학술논문

研究了一类新型网络构建问题，使有向网络中子网络的弧在切割成权值为L的分段时所产生的总分段数尽可能小。针对问题，假设有向网络每条弧的权值不小于L，给出子网络结构为有向路或强连通支撑子网络两种情形时的近似算法，并证明算法的最坏情况界分别为32和3。
연구료일류신형망락구건문제，사유향망락중자망락적호재절할성권치위L적분단시소산생적총분단수진가능소。침대문제，가설유향망락매조호적권치불소우L，급출자망락결구위유향로혹강련통지탱자망락량충정형시적근사산법，병증명산법적최배정황계분별위32화3。
This paper considers a new class of network construction problems.Given a directed network, it aims to find a subnetwork with specific structure in which arcs are cut into pieces of length at most L.The objective is to minimize the total number of pieces.When the length of each arc is no smaller than L and the network structure is restricted by a directed path or a strongly-connected spanning subnetwork, we provide approximation algorithms with worst case ratios of 32 and 3 respectively.