Max Clique nel grafico a intervalli

Question

Secondo algoritmi efficienti per grafici a intervalli e grafici arc circolari C'è una $ o (n \ log n) $ algoritmo per trovare la cricca massima in un grafico a intervalli, supponendo che tu abbia il modello di intervallo. Sfortunatamente, né il foglio né i riferimenti effettivamente elaborano su ciò che l'algoritmo è, oltre a dire che è possibile modificare l'algoritmo ben noto per grafici a intervalli in ottimale da colorare (dove si colorano avidamente il grafico nell'ordine generato ordinando gli intervalli lessicograficamente) a Calcola il Max Clique. Ciò ha senso, poiché il colore più grande utilizzato in una colorazione ottimale è la dimensione della clique massima in un grafico perfetto (e i grafici a intervalli sono perfetti). Sfortunatamente, oltre a questo, sono perso su come calcolare il Max Clique. L'altro approccio è quello di modificare alcune strutture dei dati ogni volta che aumenta il colore massimo, ma non riesco a capire esattamente quale struttura dei dati utilizzare o come modificarlo.

Qualcuno conosce un riferimento per questo algoritmo o può reinventare una descrizione di esso?

Answer 1

I grafici a intervalli sono grafici accidentali, in modo da poter utilizzare un algoritmo di tempo lineare per la ricerca di Max Clique in un grafico chordal.Questo può essere fatto prima trovando un perfetto ordine di eliminazione, e quindi usare il fatto che ogni volta che un vertice viene eliminato forma una cricca insieme ai suoi vicini che non vengono ancora eliminati.Inoltre tutte le clique maximali appaiono in questo processo.

Per trovare l'ordine perfetto per l'eliminazione, la ricerca massima della cardinalità (MCS) è l'algoritmo più semplice e funziona in tempo lineare.(Non so perché Wikipedia menziona prima lexbfs, è molto più complicato.)

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;

.

Credo che questa sia una corretta implementazione in base all'algoritmo da colorare intervallo che viene eseguito in $ o (n \ log n) $ tempo.

Se ti interessa il Max Clique, quindi può essere semplificato un po ':

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;

.