Gitterprobleme

10

Es wurde viel an Rechenproblemen für Teilaufträge gearbeitet (z. B. Erkennung, Sprungzahl, Erkennung von Vergleichbarkeitsgraphen usw.).

Ich bin gespannt, welche gitterspezifischen Arbeiten durchgeführt wurden. Ich habe mich umgesehen und nicht viel ähnliche Arbeit für Gitter gefunden.

Insbesondere interessiert mich, ob folgende Gitterprobleme untersucht wurden:

  1. Gittererkennung: Ist es bei einer DAG oder einer Teilordnung tatsächlich ein Gitter?

  2. Gittervergleichbarkeitsgraphenerkennung: Können bei einem ungerichteten Graphen G die Kanten von G so ausgerichtet werden, dass die resultierende Orientierung ein Gitter ist?

  3. Bestimmen / Zählen der nicht reduzierbaren Verknüpfungselemente eines Gitters

  4. Bestimmen, ob ein bestimmtes Gitter verteilt / modular ist

ds.algorithms reference-request graph-algorithms partial-order order-theory Travis Service
quelle
1
eine verwandte Frage: Angenommen, das Gitter wird nicht explizit dargestellt, sondern über (sagen wir) ein Nachbarschaftsorakel (
rein

Antworten:

16

Re Ihre Fragen (2 + 4): ein ungerichteter Graph G ist die Abdeckung Graph (nicht die Vergleichbarkeitsgraph!) Eines verteilten Gitter iff es sich um eine mittlere Graph und es hat zwei Scheitelpunkte, die komplementär sind (auf gegenüberliegenden Seiten jedes Djokovic Äquivalenz Klasse von Kanten); siehe Duffus, Dwight; Rival, Ivan (1983), "Als Verteilungsgitter orientierbare Graphen", Proc. AMS 88 (2): 197–200. Dies kann in einen effizienten Algorithmus umgewandelt werden, indem ein Algorithmus zur Erkennung von Mediangraphen (siehe Wikipedia-Artikel) mit einem Algorithmus zum Auffinden komplementärer Eckpunktpaare kombiniert wird (siehe Satz 3 von arxiv: cs.DS / 0206033 ).

David Eppstein
quelle
1

Hier ist ein Link, vielleicht kann er Ihnen helfen. http://fc.isima.fr/~nourine/publications.php M. Habib und L. Nourine: Ein linearer Zeitalgorithmus zum Erkennen von Verteilungsgittern, RR LIRMM, Nr. 92-012, 1992.

user53561
quelle