Puedes sugerir una buena bruto gráfico de la coloración algoritmo? ¿Cuáles son los mejores algoritmos de hoy en día?
Respuestas
¿Demasiados anuncios?
Pat Notz
Puntos
46841
Un interesante algoritmo de aproximación es la del Wigderson. Se muestra cómo el color de una 3-engañosa gráfico con $O(\sqrt{n})$ colores. Es muy sencillo:
Si el grado máximo es de menos de $\sqrt{n}$, ya está hecho (sólo el color con avidez). Si hay un nodo de grado mayor que $\sqrt{n}$, usted sabe que el barrio es de dos engañosa y dos de color y nunca uso los colores de nuevo. Quitar el vértice y sus vecinos de la gráfica y continuar.
Ha habido varios seguimiento de obras por Blum y las mejoras más recientes de uso semidefinite de programación.
Véase, por ejemplo, http://www.cs.cmu.edu/~anupamg/adv-aprox/lecture15.pdf
o,
http://www.cs.princeton.edu/~chlamtac/acc-stoc.ps
para el semidefinite enfoque de programación.
Hugo
Puntos
2156
Hay una serie de heurísticas que funcionan bastante bien. Todos ellos trabajan por la prescripción de algún tipo de ordenamiento en los vértices, y luego colorear los vértices de uno por uno, utilizando la menor sin usar color para el siguiente.
- Primer Ajuste no precisamente el de arriba, con una inicial arbitraria de pedidos. Es rápido, pero es necesario decir que realiza bastante mal.
- LDO órdenes de los vértices en orden decreciente de grado, con la idea de que el alto grado de los vértices pueden ser de color más fácilmente.
- SDO (grado de saturación de pedidos) es una variante LDO donde los vértices son ordenados en orden decreciente por "saturación de grado", que se define como el número de colores distintos en el vértice del vecindario.
- IDO (grado de incidencia de pedido) es una variante de la SDO, donde el "grado" de un vértice se define como el número de colores de los vértices de su barrio.
Los dos últimos heurística exigir el fin de ser reconstruido después de cada paso, y por tanto son más caros, pero no hay evidencia empírica que sugiere que lo hacen razonablemente bien, sobre todo en paralelo.
Ninguno de estos algoritmos incluyen ningún tipo de garantías formales, por lo que se advierte.
Doug
Puntos
858
Dylan
Puntos
872
En la práctica no es la óptima fines usted puede ser que desee mirar a DSATUR, y en el presente documento, que describe brevemente algunos métodos sencillos: http://www.math.tu-clausthal.de/Arbeitsgruppen/Diskrete-Optimierung/publications/2002/gca.pdf
user16683
Puntos
46
