Representasi paling sederhana untuk grafik menggunakan matriks / daftar adjacency, yang berarti bahwa setiap node dan edge secara eksplisit diwakili. Pentingnya representasi implisit untuk grafik yang menunjukkan keteraturan yang kuat telah lama diakui. Misalnya, Galperin & Wigderson (1983), Papadimitriou & Yannakakis ( Catatan tentang Representasi Ringkas Grafik , 1986) mengeksplorasi pertanyaan grafik yang matriks kedekatannya diwakili oleh rumus Boolean yang menjawab apakah (i, j) adalah edge atau tidak. diberikan representasi biner dari nomor simpul i dan j. Di bawah beberapa kendala yang umumnya dipenuhi pada reduksi, masalah P-complete untuk grafik eksplisit menjadi PSPACE-complete untuk representasi ini, masalah NP-complete menjadi NEXPTIME-complete, dll.
Pendekatan alami untuk grafik reguler tersebut adalah untuk mewakili formula Boolean menggunakan ROBDD; kesulitannya adalah bahwa algoritma klasik cenderung menghitung satu per satu node, yang menimbulkan biaya eksponensial pada representasi seperti itu dan dengan demikian harus dihindari. Telah ada makalah yang diterbitkan tentang masalah klasik yang diselesaikan dengan menggunakan representasi seperti itu, misalnya Gentilini et al. ( Komputasi komponen yang sangat terhubung dalam jumlah linier langkah simbolis ), Woelfel ( Penyortiran topologi simbolik dengan OBDD ).
Saya bertanya-tanya apakah ada beberapa survei teknik seperti itu, karena itu tidak nyaman untuk mengeruk literatur sedemikian rupa ...
sumber