Problemy z kratą

10

Dużo pracy poświęcono problemom obliczeniowym dla zamówień częściowych (np. Rozpoznawanie, numer skoku, rozpoznawanie wykresu porównywalności itp.).

Jestem ciekawy, jaką pracę wykonano dla sieci. Szukałem wokoło i nie znalazłem podobnej pracy dla krat.

W szczególności jestem zainteresowany tym, czy zbadano następujące problemy z siecią:

  1. Rozpoznawanie krat: czy przy danym DAG czy częściowym zamówieniu jest to w rzeczywistości sieć?

  2. Rozpoznawanie wykresu porównywalności kratowej: czy biorąc pod uwagę niekierowany wykres G, czy krawędzie G mogą być zorientowane tak, aby wynikowa orientacja była siatką?

  3. Wyznaczanie / zliczanie połącz nieredukowalnych elementów sieci

  4. Ustalenie, czy dana sieć jest rozproszona / modułowa

ds.algorithms reference-request graph-algorithms partial-order order-theory Travis Service
źródło
1
powiązane pytanie: załóżmy, że sieć nie jest wyraźnie pokazana, ale poprzez (powiedzmy) wyrocznię sąsiedzką (wchodzi i wychodzi)
Suresh Venkat

Odpowiedzi:

16

Odpowiadaj na pytania (2 + 4): niekierowany wykres G jest wykrywającym (nie wykresem porównywalności!) Siatki rozproszonej, jeśli jest to wykres mediany i ma dwa wierzchołki, które są komplementarne (po przeciwnych stronach każdej równoważności Djokovica klasa krawędzi); patrz Duffus, Dwight; Rival, Ivan (1983), „Wykresy zorientowane jako sieci dystrybucyjne”, Proc. AMS 88 (2): 197–200. Można to zmienić w skuteczny algorytm, łącząc algorytm rozpoznawania wykresu mediany (patrz artykuł z Wikipedii) z algorytmem znajdowania komplementarnych par wierzchołków (patrz twierdzenie 3 arxiv: cs.DS / 0206033 ).

David Eppstein
źródło
1

Oto link, który może ci pomóc. http://fc.isima.fr/~nourine/publications.php M. Habib i L. Nourine: Algorytm czasu liniowego do rozpoznawania krat dystrybucyjnych, RR LIRMM, nr 92-012, 1992.

użytkownik53561
źródło