间隔图中的最大集团

Question

根据间隔图和圆弧图的高效算法假设您拥有间隔模型，有一个 $ o（n \ log n）$ 算法，用于在一个间隔图中找到max clique。不幸的是，纸张和参考资料都没有详细说明算法是什么，除了说您可以修改众所周知的算法以获得最佳着色区间图（其中您以通过排序的排列方式排序的顺序贪婪地彩色图形）到计算max clique。这是有道理的，因为在最佳着色中使用的最大颜色是完美图中最大集团的大小（并且间隔图是完美的）。不幸的是，除此之外，我遗失了如何计算Max Clique。明显的方法是每次最大颜色增加时修改一些数据结构，但我无法精确地弄清楚使用什么数据结构或如何修改它。

有谁知道该算法的参考或可以重新发明它的描述？

Answer 1

间隔图是Chordal图形，因此您可以使用线性时间算法来查找Chordal图表中的Max Clique。这可以通过首先找到完美的消除排序来完成，然后使用每当顶点被消除的事实，它与其邻居一起形成一个集团。此外，所有最大族织都会出现在此过程中。

为了找到完美的消除排序，最大基数搜索（MCS）是最简单的算法，它在线性时间工作。（我不知道为什么维基百科提到lexbfs首先，它更复杂。）

Answer 2

def mex(m):
  for i in [0 ..]:
    if not(m.contains(i)):
      return i

def maxCliqueOfIntervals(intervals):
  maxClique = []
  map = {}
  for interval in intervals.sort():
    // map should only contain intervals that overlap with the current interval
    map.filter(lambda x: overlaps(x, interval));
    // choose the smallest color not in the map to color the current interval
    map.insert(mex(map), interval);
    // the map now comprises a clique, if it is larger than the current max clique,
    // replace the max clique with the current map
    if map.size() > maxClique.size():
      maxClique = map.elems();
  return maxClique;

.

我相信这是基于在 $ o（n \ log n）$ 时间中运行的间隔着色算法的正确实现。

如果您只关心Max Clique，那么它可以简化一点：

def maxCliqueOfIntervals(intervals):
  maxClique = []
  active = []
  for interval in intervals.sort():
    active.filter(\x -> overlaps(x, interval));
    active.push(interval);
    if active.size() > maxClique.size():
      maxClique = active;
  return maxClique;

.