請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38355
標題: Minimum Cut for Circular-arc Graphs
作者: D.T.Lee
M.Sarrafzadeh
Y.F.Wu
關鍵字: computational complexity
algebraic computation trees
circular-arc graphs
circle graphs
minimum covering
maximum independent set
摘要: 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].
URI: http://hdl.handle.net/11455/38355
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。