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

Revision en3, by 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?

Tags clique

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Aveiro_quanyue 2023-03-30 09:51:40 22
en3 English Aveiro_quanyue 2023-03-30 09:51:10 10
en2 English Aveiro_quanyue 2023-03-30 09:50:43 72 (published)
en1 English Aveiro_quanyue 2023-03-30 09:50:11 648 Initial revision (saved to drafts)