We define the edge-disjoint trail cover problem (EDTC) which covers all vertices in the given graph G = (V,E) with minimum number of edge-disjoint trails. We prove that EDTC is NP-complete and show an algorithm of O (|V|+|E|) time complexity for finding minimum edge-disjoint trail cover on triangulated graphs. an application of EDTC is shown, which is called board assembly problem. The problem arises from the factory automation to assemble a printed circuit board and a number of chips. We also prove the board assembly problem is NP-complete.
본 논문에서는 Edge-Disjoint Trail Cover 문제를 새로이 정의하였다. EdgeDisjoint Trail Cover는 주어진 그래프의 모든 정점들을 커버하는 최소 갯수의 edge-disjoint한 trail들을 찾는 문제이다. 이 문제가 NP-complete임을 증명하고 특별히 triangulated 그래프에 대해서 O(|V|+|E|)의 시간 복잡도를 갖는 알고리즘을 제시하였다. 이 문제의 응용으로서 프린트된 기판과 칩들을 조립하는 최적 순서를 찾는 문제(Board Assembly Problem)를 보이고 Edge-Disjoint Trail Cover 문제로 변환됨을 보였다.
