Please use this identifier to cite or link to this item:
|標題:||Efficient Algorithms for Interval Graphs and Circular-arc Graphs||作者:||U.I.Gupta
|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.
|Appears in Collections:||資訊科學與工程學系所|
Show full item record
TAIR Related Article
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.