O(n(logn)^k) algorithm for maximum interval cliques?

Правка en3, от Aveiro_quanyue, 2023-03-30 09:51:10

We have a lot of $$$n$$$ closed intervals. We need to find a set of intervals with maximum cardinality such that the intervals in this set intersect pairwise.

As far as I know, we can use the famous greedy algorithm to solve the maximum interval independent set problem, i.e., the interval scheduling problem. But how about the maximum interval clique problem? We can convert it into an interval graph which is also chordal, and find the maximum clique using LexBFS in $$$O(n^2)$$$ time as the number of edges in the interval graph is $$$O(n^2)$$$. What about an $$$O(nlog^kn)$$$ algorithm? Am I overthinking?

Теги clique

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Aveiro_quanyue 2023-03-30 09:51:40 22
en3 Английский Aveiro_quanyue 2023-03-30 09:51:10 10
en2 Английский Aveiro_quanyue 2023-03-30 09:50:43 72 (published)
en1 Английский Aveiro_quanyue 2023-03-30 09:50:11 648 Initial revision (saved to drafts)