Masalah kisi

10

Ada cukup banyak pekerjaan pada masalah komputasi untuk pesanan parsial (misalnya, pengakuan, nomor lompatan, pengakuan grafik komparatif, dll ...).

Saya ingin tahu apa pekerjaan khusus untuk kisi telah dilakukan. Saya telah mencari-cari dan tidak menemukan banyak pekerjaan serupa untuk kisi-kisi.

Secara khusus, saya tertarik pada apakah masalah kisi berikut telah diselidiki:

  1. Pengenalan kisi: diberi DAG atau perintah parsial, apakah ini sebenarnya kisi?

  2. Pengenalan grafik komparabilitas kisi: diberi grafik G tidak berarah, dapatkah tepi G diorientasikan sedemikian rupa sehingga orientasi yang dihasilkan adalah kisi?

  3. Menentukan / menghitung elemen gabungan kisi yang tidak dapat direduksi

  4. Menentukan apakah kisi yang diberikan didistribusikan / modular

ds.algorithms reference-request graph-algorithms partial-order order-theory Layanan Travis
sumber
1
pertanyaan terkait: misalkan kisi tidak disajikan secara eksplisit, tetapi melalui (katakanlah) oracle lingkungan (masuk dan keluar)
Suresh Venkat

Jawaban:

16

Berikan pertanyaan Anda (2 + 4): grafik tidak berarah G adalah grafik penutup (bukan grafik komparatif!) Dari kisi yang didistribusikan jika itu adalah grafik median dan memiliki dua simpul yang saling melengkapi (pada sisi yang berlawanan dari setiap ekivalensi Djokovic kelas tepi); lihat Duffus, Dwight; Rival, Ivan (1983), "Grafik berorientasi sebagai kisi distributif", Proc. AMS 88 (2): 197–200. Ini dapat diubah menjadi algoritma yang efisien dengan menggabungkan algoritme pengenalan grafik median (lihat artikel Wikipedia) dengan algoritma untuk menemukan pasangan simpul komplementer (lihat teorema 3 dari arxiv: cs.DS / 0206033 ).

David Eppstein
sumber
1

Berikut ini tautannya, semoga bisa membantu Anda. http://fc.isima.fr/~nourine/publications.php M. Habib dan L. Nourine: Algoritma Waktu Linier untuk Mengenali Kisi Distributor, RR LIRMM, No 92-012, 1992.

pengguna53561
sumber