Minimum cuts for circular-arc graphs

作者： D. T. Lee , M. Sarrafzadeh , Y. F. Wu

DOI: 10.1137/0219071

关键词:

摘要: The problem of finding a minimum cut n arcs on unit circle is considered. It shown that this can be solved in $\Theta (n \log n)$ time, which optimal to within constant factor. If the endpoints are sorted, linear time. solution used solve new facility competitive location and partition set for intersection model graph. As by-product it also maximum independent obtained assuming much simpler than most recent result Masuda Nakajima [SIAMI. Comput., 17 (1988), pp. 41–52].