請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38460
標題: Efficient Algorithms for Interval Graphs and Circular-arc Graphs
作者: U.I.Gupta
D.T.Lee
J.Y.T.Leung
摘要: We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in O(n log n) time [O(n) time if the endpoints of the intervals are sorted]. For the more general circular-arc graphs, a maximum independent set and a minimum covering by disjoint completely connected sets or cliques can be found in O(n2) time, provided again that a corresponding family of arcs is given.
URI: http://hdl.handle.net/11455/38460
顯示於類別:資訊科學與工程學系所

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


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