Please use this identifier to cite or link to this item:
標題: Minimum Cut for Circular-arc Graphs
作者: D.T.Lee
關鍵字: computational complexity;algebraic computation trees;circular-arc graphs;circle graphs;minimum covering;maximum independent set
Project: SIAM J. Computing, Volume�19, Issue�6, Page(s) �1041-1050.
The problem of finding a minimum cut of n arcs on a unit circle is considered. It is shown
that this problem can be solved in (R)(n log n) time, which is optimal to within a constant factor. If the
endpoints of the arcs are sorted, the problem can be solved in linear time. The solution to the minimum
cut problem can be used to solve a minimum new facility problem in competitive location and a minimum
partition set problem for the intersection model of a circle graph. As a by-product it is also shown that the
maximum independent set of n arcs can be obtained in linear time, assuming the endpoints are sorted,
which is much simpler than the most recent result of Masuda and Nakajima [SIAM J. Comput., 17 (1988),
pp. 41-52].
DOI: 10.1137/0219071
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.