Saya ingin tahu apakah ada algoritma sublinear untuk membuat penghapusan atau kontraksi tepi dalam embedding kombinatorial , katakanlah, grafik planar?
Karena dalam penyertaan kombinatorial kita harus mempertahankan simpul G dan G * pada saat yang sama, dengan mempertimbangkan bahwa kontraksi dalam primal adalah penghapusan dalam dual, itu cukup hanya untuk membuat penghapusan, memperbarui permutasi primer sesuai dengan dual dan sebaliknya. . Tetapi cara yang jelas untuk melakukannya adalah hanya menghitung ulang mereka, yang membutuhkan waktu linier. Bisakah kita melakukan yang lebih baik?
Pertanyaan kedua : apakah ada teknik yang membantu menyingkirkan banyak sisi antara simpul yang sama? (satu-satunya solusi yang saya lihat untuk masalah kedua adalah menunda penghapusan beberapa sisi sampai kita mendapatkan grafik dengan, misalnya, m = 6n, di mana m - jumlah tepi, n - jumlah simpul, ini akan membuat waktu diamortisasi O (1)) Mungkin ada beberapa teknik, yang dapat membuat waktu ini tidak diamortisasi? (Saya juga tertarik hanya pada o (n) solusi, belum tentu O (1))
Terima kasih banyak!
Jawaban:
Pertanyaan ini tidak lengkap tanpa menentukan informasi apa tentang grafik saat ia mengubah Anda ingin struktur data grafik dinamis Anda untuk output atau permintaan dukungan untuk. Tetapi makalah berikut ini mungkin relevan, meskipun dijelaskan dalam pengaturan yang lebih umum dari kombinasi kombinatorial dalam genus sewenang-wenang daripada hanya planar. Ini pasti mendukung kontraksi dan penghapusan, serta operasi terbalik mereka, dalam waktu logaritmik per operasi.
Generator dinamis dari grafik yang disematkan secara topologis. D. Eppstein. arXiv: cs.DS / 0207082 . SODA 2003, hlm. 599-608.
Adapun pertanyaan kedua: Saya tidak melihat bagaimana menangani beberapa adjacencies secara umum, tetapi mudah untuk menyingkirkan bigons (beberapa tepi tanpa apa-apa di antara mereka) karena mereka hanya dapat datang dari dua wajah yang ada di kedua sisi tepi yang dikontrak atau dari wajah yang mengelilingi tepi yang dihapus. Itu harus cukup untuk banyak tujuan karena menyingkirkan bigons memastikan bahwa grafik yang tersisa memiliki sejumlah tepi sebanding dengan jumlah simpulnya.
sumber