Centru2

Considerăm intervalele noduri ale unui graf şi vom adăuga muchie între două noduri dacă intervalele corespunzatoare se suprapun. Pe acest graf, ne propunem sa determinăm cea mai mică lexicografic mulţime independentă maximală de vârfuri (maximum independence set sau MIS).
Pentru claritatea explicaţiei vom presupune ca nu există intervale complet incluse unul în celălalt. Algoritmul care tratează şi acest caz urmează aproximativ la fel paşii celui prezentat în continuare.
Sortăm intervalele după capătul din dreapta. Definim D[i] = min{j > i | i si j nu sunt legate printr-o muchie}. Vom construi o subrutina MIS{i,j} pe care o vom utiliza ulterior şi care va determina cardinalul MIS-ului vârfurilor din graf curprinse între i şi j, i ≤ j. Se observă că MIS{i,j} = 1 + max{k | Dk[i] ≤ j}. Vom construi o matrice R[i][j] = D^{2^i}[j], cu ajutorul căreia vom determina biţii rezultatului (asemănător cu modul de funcţionare al căutarii binare bazate pe ideea lui Mihai Pătraşcu prezentată în acest articol).
Parcurgem nodurile în ordinea iniţială. Fie i0 primul nod. Fie i, i+1, ..., j vecinii nodului i0. Aceştia pot fi determinaţi în O(logN) folosind cautare binară. Nodul i0 poate face parte din soluţie dacă şi numai dacă MIS{1, i-1} + 1 + MIS{j+1, N} = MIS{1, N}. Această verificare poate fi făcută în complexitate O(logN) folosind subrutina descrisă mai sus. Să presupunem în continuare că nodul i0 a trecut testul. Luăm apoi nodul i1, următorul în ordinea iniţială. Dacă i1 aparţine intervalului [i, j], el nu aparţine soluţiei deoarece ar intra în conflict cu nodul ales precedent. Să presupunem că i1 apartine intervalului [j+1, N] şi vecinii acestuia sunt p, p+1, ..., q, unde j < p ≤ q ≤ N. Trebuie din nou verificat dacă MIS{j+1, N} = MIS{j+1, p-1} + 1 + MIS{q+1, N}. Este intuitiv că acest algoritm conduce la obţinerea MIS-ului minim lexicografic.
Pentru a realiza operaţiile descrise mai sus in timp logaritmic este nevoie de un arbore de intervale cu ajutorul căruia sa verificăm dacă noile intervale se intersectează cu cele deja existente în soluţie şi un arbore binar echilibrat de căutare (treap, AVL sau set din STL) pentru a localiza intervalele pe care trebuie făcute verificările.