Teoretyczne informatyka transitive-closure

1

Zamykanie przechodnie online lepiej niż O (N ^ 2) na dodanie krawędzi

Szukam algorytmu online, aby utrzymać przechodnie przechodzenie ukierunkowanego wykresu acyklicznego o złożoności czasowej mniejszej niż O (N ^ 2) na dodanie krawędzi. Mój obecny algorytm wygląda następująco: For every new edge u->v connect all nodes in Pred(u) \cup { u } with all nodes in Succ(v) \ \cup { v …

15 ds.algorithms graph-theory ds.data-structures transitive-closure

2

Obliczanie przejściowego zakończenia / wyroku istnienia ścieżki

Było kilka pytań ( 1 , 2 , 3 ) na temat przechodniego uzupełniania, które zmusiły mnie do zastanowienia się, czy coś takiego jest możliwe: Załóżmy, że otrzymujemy wykres skierowany na dane wejściowe GsolG i chciałby odpowiedzieć na zapytania typu „(u,v)∈G+(u,v)∈sol+(u,v)\in G^+? ”, tzn. pytając, czy istnieje krawędź między dwoma …

9 graph-theory graph-algorithms space-time-tradeoff transitive-closure

5

Kontrola przechodniości a zamknięcie przechodnie

Czy sprawdzenie przechodniości digrapha nie jest łatwiejsze niż (pod względem asymptotycznej złożoności) przyjęcie przejścia przechodniego digrapha? Czy znamy dolną granicę lepiej niż aby ustalić, czy digraf jest przechodni?Ω(n2)Ω(n2)\Omega(n^2)

9 graph-theory directed-acyclic-graph transitive-closure

Pytania otagowane jako transitive-closure