本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #767
- 日期：2026-03-18
摘要
透過微分方程逼近馬可夫鏈平均路徑的技術已被證明是分析隨機圖實例啟發式效能的有用工具。然而，由於需要在原始狀態空間內保持均勻的隨機性，目前只能用這種方法分析一小部分演算法。在這裡，我們透過展示如何將其推廣到處理優先考慮高度或低度頂點的啟發式方法，顯著擴展了微分方程技術的範圍。我們特別關註三色並分析實際上成功的 Brelaz 啟發式的「平滑」版本。這可以證明幾乎所有具有平均度 $d$ 的圖，即 $G(n,p=d/n)$，對於 $d \leq 4.03$ 都是 3-可著色的，並且幾乎所有 4-正則圖都是 3-可著色的。這比 $G(n,p=d/n)$ 的 3-可著色性閾值的先前下限 $3.847$ 有所改進，並給出了隨機正則圖可著色性的第一個重要結果。事實上，我們的方法可用於處理「任意」稀疏度分佈，並與偏好高度或低度頂點的通用圖演算法結合使用。