Tinjauan Singkat tentang Algoritma Jalur Terpendek Modern dan Teknik Optimasi Graf

Tabel Tautan

Abstrak dan 1. Pendahuluan

1.1 Kontribusi Kami

1.2 Pengaturan

1.3 Algoritma

1. Karya Terkait

2. Algoritma

   3.1 Fase Dekomposisi Struktural

   3.2 Fase Perutean

   3.3 Varian WormHole

3. Analisis Teoretis

   4.1 Pendahuluan

   4.2 Sublinearitas Cincin Dalam

   4.3 Kesalahan Aproksimasi

   4.4 Kompleksitas Kueri

4. Hasil Eksperimental

   5.1 WormHole𝐸, WormHole𝐻 dan BiBFS

   5.2 Perbandingan dengan metode berbasis indeks

   5.3 WormHole sebagai primitif: WormHole𝑀

Referensi

2 KARYA TERKAIT

Ada banyak penelitian tentang jalur terpendek dan jarak, yang mencakup beberapa dekade, dan termasuk ratusan algoritma dan heuristik yang dirancang untuk berbagai pengaturan. Di sini, kami hanya meninjau beberapa karya yang paling terkait dengan karya kami. Untuk gambaran yang lebih komprehensif, lihat survei [42, 55] dan referensi di dalamnya.

\ Pendekatan berbasis indeks. Seperti disebutkan sebelumnya, serangkaian algoritma yang umum digunakan didasarkan pada pendekatan landmark/sketsa [37, 61, 62], dengan Pruned Landmark Labeling (PLL) [5] mungkin yang paling berpengaruh. Algoritma ini mengikuti prosedur dua langkah: langkah pertama menghasilkan pengurutan vertex berdasarkan kepentingan (berdasarkan heuristik yang berbeda), dan langkah kedua menghasilkan pelabelan dari pohon jalur terpendek yang dipangkas yang dibangun sesuai dengan pengurutan. Kemudian jarak terpendek antara sepasang vertex 𝑠 dan t dapat dijawab dengan cepat berdasarkan label mereka. Namun, bahkan dengan pemangkasan, PLL membutuhkan waktu pengaturan yang signifikan. Oleh karena itu, telah ada banyak upaya untuk memparalelkannya [29, 37, 39].

\ Pendekatan berbasis embedding. Beberapa pendekatan terbaru memanfaatkan embedding graf untuk memperkirakan jalur terpendek. Seperti dalam pembelajaran representasi, mereka berusaha menemukan representasi yang efisien dari jarak antara pasangan node [64, 65]. Lini kerja modern juga mempertimbangkan embedding hiperbolik dari graf, yang terkait erat dengan dekomposisi pohon, untuk menjawab pertanyaan jalur terpendek [11, 33]. Karya terbaru juga telah melihat percepatan proses ini dengan menggunakan metode pembelajaran mendalam berbasis GPU [35, 47, 48]. Query-by-Sketch [57] mempertimbangkan tugas yang terkait tetapi tidak sebanding, yaitu menjawab pertanyaan graf jalur terpendek, di mana tujuannya adalah menghitung subgraf yang berisi tepat semua jalur terpendek antara sepasang vertex yang diberikan. Mereka mengusulkan skema pelabelan alternatif untuk meningkatkan skalabilitas dan waktu pertanyaan.

\

\ Pendekatan berbasis inti-periferi. Beberapa karya lain memanfaatkan struktur inti-periferi dari jaringan [6, 13, 38]. Brady dan Cohen [13] menggunakan skema perutean kompak untuk merancang algoritma dengan kesalahan aditif kecil berdasarkan kemiripan periferi dengan hutan. Akiba, Sommer dan Kawarabayashi [6] memanfaatkan properti lebar pohon rendah di luar inti, dan di [38], para penulis merancang indeks berbasis Core-Tree untuk meningkatkan waktu pra-pemrosesan pada graf masif. Kami mencatat bahwa dalam semua hasil ini, overhead memori bersifat super-linear.

\ Graf kasus terburuk. Di sisi teoretis, telah ada banyak hasil pada jalur terpendek yang tepat dan perkiraan dalam graf kasus terburuk, misalnya, [19, 20, 22, 49, 51, 67], dengan peningkatan baru-baru ini dalam tahun terakhir. Sebagian besar dari ini berfokus pada kasus 2-aproksimasi, yang pertama kali diselidiki dalam karya seminal Aingworth et al. [4]. Kami mengarahkan pembaca ke survei Zwick [66] tentang algoritma jalur terpendek yang tepat dan perkiraan, dan survei Sen [53] tentang oracle jarak untuk graf umum dengan penekanan pada penurunan biaya pra-pemrosesan. Terutama, karena kami membuat asumsi struktural di luar kasus terburuk yang umum dalam jaringan besar, yaitu, struktur inti-periferi, baik hasil kami maupun algoritma kami secara substansial berbeda dari literatur teoretis kasus terburuk.

\

:::info Penulis:

(1) Talya Eden, Universitas Bar-Ilan ([email protected]);

(2) Omri Ben-Eliezer, MIT ([email protected]);

(3) C. Seshadhri, UC Santa Cruz ([email protected]).

:::

:::info Makalah ini tersedia di arxiv di bawah lisensi CC BY 4.0.

:::

\