基于度的逻辑邻接检查法，高效减少图着色颜色数。
Degree-Based Logical Adjacency Checking (DBLAC): A Novel Heuristic for Vertex Coloring
- 用顶点度和逻辑与操作优化着色顺序
- 在标准图上比DSATUR和RLF少用颜色且更快
- 适合需要高效图着色的应用场景
本文提出一种基于度的逻辑邻接检查方法（DBLAC），通过独特的逻辑与操作实现高效图着色。该方法在顶点间存在公共边时表现出更优的颜色分配能力，显著减少产生的颜色数量。我们对DBLAC的时间与空间复杂度进行了详细理论分析，并在标准基准图集上进行长期实验验证其有效性。结果表明，相较于现有算法如DSATUR和递归最大团法（RLF），DBLAC在颜色使用数和运行时间方面均达到竞争力水平。
原文摘要 · Abstract (English)
Degree Based Logical Adjacency Checking (DBLAC). An efficient coloring of graphs with unique logical AND operations. The logical AND operation shows more effective color assignment and fewer number of induced colors in the case of common edges between vertices. In this work, we provide a detailed theoretical analysis of DBLAC's time and space complexity. It furthermore shows its effectiveness through prolonged experiments on standard benchmark graphs. We compare it with existing algorithms, namely DSATUR and Recursive Largest First (RLF). Second, we show how DBLAC achieves competitive results with respect to both the number of colors used and runtime performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。