Max clique en gráfico de intervalo

Question

Según algoritmos eficientes para gráficos de intervalo y gráficos de arco circular Hay un $ o (n \ log n) $ algoritmo para encontrar la CLÍA MAX en un gráfico de intervalo, asumiendo que tiene el modelo de intervalo. Desafortunadamente, ni el documento ni las referencias en realidad elaboran en cuál es el algoritmo, más allá de decir que puede modificar el algoritmo conocido para los gráficos de intervalo de coloración de manera óptima (donde coloree con avidez la gráfica en el orden generado al clasificar los intervalos de léxico) a calcular la camarilla máxima. Esto tiene sentido, ya que el color más grande utilizado en una coloración óptima es el tamaño de la CLÍA MAX en un gráfico perfecto (y los gráficos de intervalo son perfectos). Desafortunadamente, más allá de eso, estoy perdido en cuanto a cómo calcular la camarilla máxima. El enfoque obvio es modificar alguna estructura de datos cada vez que aumenta el color máximo, pero no puedo averiguar con precisión qué estructura de datos usar o cómo modificarla.

¿Alguien conoce una referencia para este algoritmo o puede reinventar una descripción de la misma?

Answer 1

Los gráficos de intervalo son gráficos cordales, por lo que puede usar un algoritmo de tiempo lineal para encontrar max clique en un gráfico de cordas.Esto se puede hacer para encontrar primero una orden de eliminación perfecta, y luego usar el hecho de que cada vez que se elimina un vértice, forma una camarilla junto con sus vecinos que aún no se eliminan.Además, todas las camarillas máximas aparecen en este proceso.

Para encontrar la orden de eliminación perfecta, la búsqueda máxima de cardinalidad (MCS) es el algoritmo más simple y funciona en tiempo lineal.(No sé por qué Wikipedia menciona primero a Lexbfs, es mucho más complicado).

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;

Creo que esta es una correcta implementación basada en el algoritmo de coloración de intervalos que se ejecuta en $ o (n \ log n) $ tiempo.

Si acaba de preocuparse por la CLÍA MAX, entonces se puede simplificar un poco:

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;