Problemy z kratą

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

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 ).

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.