Please use this identifier to cite or link to this item: 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
Project: Networks, Volume�12, Page(s) �459-467.
摘要: 
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
DOI: 10.1002/net.3230120410
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check

Altmetric

Altmetric


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