http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
Computing a Minimum-Dilation Spanning Tree is NP-hard
Otfried Cheong(정지원),Herman Haverkort,Mira Lee(이미라) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.2A
Given a set S of n points in the plane, a minimum-dilation spanning tree of S is a tree with vertex set S of smallest possible dilation. We show that given a set S of n points and a dilation δ > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most δ exists.