米斯拉-格里斯边着色算法 米斯拉格里斯边着色算法是图论算法的一种能够在多项式时间内找到任意图的一种边着色方案这种着色算法最多使用 Δ   displaystyle Delta  种颜色 Δ displaystyle Delta  是该图节点的最大度数这对于一些图而言是最优的根据Vizing定理最坏情况下这种算法给出的结果比最优值多使用一种颜色 该算法由Jayadev Misra和戴维格里斯英语David Gries在年首次提出是对Béla Bollobás提出的一种算法的简化 对于边着色问题该算法是已知最快的几乎最优算法时间复杂度为 O   E   V   displaystyle OEV 更小的时间复杂度 O   E   V  log   V   displaystyle OEsqrt Vlog V 在年Gabow等的一篇科技报告中提出但从未被发表 总体上来说最优边着色问题是NP完全的所以很可能并不存在多项式时间内的算法同时也有指数级的算法给出了该问题的最优解