组合数学
图形着色
数学
邻接矩阵
贪婪着色
列表着色
边着色
二部图
分数着色
离散数学
完全着色
图形功率
折线图
图形
作者
Bengt Aspvall,John R. Gilbert
出处
期刊:SIAM journal on algebraic and discrete methods
[Society for Industrial and Applied Mathematics]
日期:1984-12-01
卷期号:5 (4): 526-538
被引量:56
摘要
Determining whether the vertices of a graph can be colored using k different colors so that no two adjacent vertices receive the same color is a well-known NP-complete problem. Graph coloring is also of practical interest (for example, in estimating sparse Jacobians and in scheduling), and many heuristic algorithms have been developed. We present a heuristic algorithm based on the eigenvalue decomposition of the adjacency matrix of a graph. Eigenvectors point out “bipartite-looking” subgraphs that are used to refine the coloring to a valid coloring. The algorithm optimally colors complete k-partite graphs and certain other classes of graphs with regular structure.
科研通智能强力驱动
Strongly Powered by AbleSci AI