New Methods to Color the Vertices of a Graph Export

@article{citeulike:6083384, abstract = {This paper describes efficient new heuristic methods to color the vertices of a graph which rely upon the comparison of the degrees and structure of a graph. A method is developed which is exact for bipartite graphs and is an important part of heuristic procedures to find maximal cliques in general graphs. Finally an exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs, and the new heuristic methods, the classical methods, and the exact method are compared.}, address = {New York, NY, USA}, author = {Br\'{e}laz, Daniel}, citeulike-article-id = {6083384}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=359094.359101}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/359094.359101}, doi = {10.1145/359094.359101}, issn = {0001-0782}, journal = {Communications of the ACM}, keywords = {graph\_coloring, heuristic\_search}, number = {4}, pages = {251--256}, posted-at = {2009-11-07 22:20:31}, priority = {2}, publisher = {ACM}, title = {{New Methods to Color the Vertices of a Graph}}, url = {http://dx.doi.org/10.1145/359094.359101}, volume = {22}, year = {1979} }

TY - JOUR ID - citeulike:6083384 L3 - citeulike-article-id:6083384 N2 - This paper describes efficient new heuristic methods to color the vertices of a graph which rely upon the comparison of the degrees and structure of a graph. A method is developed which is exact for bipartite graphs and is an important part of heuristic procedures to find maximal cliques in general graphs. Finally an exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs, and the new heuristic methods, the classical methods, and the exact method are compared. IS - 4 JF - Communications of the ACM SN - 0001-0782 AD - New York, NY, USA EP - 256 TI - {New Methods to Color the Vertices of a Graph} PB - ACM VL - 22 SP - 251 KW - graph_coloring KW - heuristic_search AU - Brélaz, Daniel PY - 1979/// UR - http://dx.doi.org/10.1145/359094.359101 ER -