TLDR
Algoritma baru dapat mewarnai graf hampir secepat mungkin, berdasarkan jumlah garis. Penelitian ini merupakan kemajuan signifikan dalam teori graf yang telah ada selama beberapa dekade. Tim peneliti berencana untuk mengembangkan algoritma lebih lanjut untuk mencapai waktu mewarnai yang lebih optimal. Bayangkan Anda bertugas mengatur pergerakan pesawat di bandara untuk mencegah tabrakan saat pesawat bergerak menuju atau dari landasan pacu. Para peneliti menggunakan konsep matematika bernama pewarnaan grafik, dimana jalur pesawat diubah menjadi garis yang harus diberi warna berbeda agar pesawat tidak berada di tempat yang sama pada waktu bersamaan.Selama 40 tahun, algoritma pewarnaan grafik yang ada relatif lambat dan sulit diperbaiki lebih jauh. Namun, pada tahun 2024 muncul beberapa algoritma baru yang secara signifikan lebih cepat, membuka jalan untuk inovasi yang lebih besar lagi dalam mengatur pergerakan pesawat dan masalah serupa.Tim peneliti yang terdiri dari beberapa ahli seperti Sepehr Assadi, Martín Costa, dan Soheil Behnezhad berhasil menciptakan algoritma yang hampir mencapai kecepatan optimal. Algoritma ini hanya bergantung pada jumlah jalur yang harus diwarnai, bukan pada jumlah titik tempat jalur itu terhubung.Rahasia kecepatan algoritma ini adalah teknik priming yang mengubah keadaan grafik dengan pendekatan randomisasi, serupa dengan mengecat dinding dengan dasar sebelum lapisan akhir. Setelah sebagian besar grafik diwarnai secara acak, sisa area dapat diwarnai hampir bersamaan secara mudah sehingga mempercepat proses secara drastis.Walau demikian, para peneliti masih berupaya meningkatkan algoritma agar tidak bergantung pada randomisasi dan menghilangkan faktor logaritmik untuk membuatnya benar-benar linear. Hasil ini merupakan pencapaian besar di bidang teori komputasi dan membantu memahami bagaimana mengelola sistem kompleks seperti bandara yang besar.
