7
Encontré muchos problemas que pueden formularse como un problema de gráfico. En general es NP-hard pero a veces el gráfico puede ser plano. Por lo tanto, estoy interesado en aprender estos problemas y los algoritmos.Lista de problemas que, en general, son NP-hard pero tienen solución de tiempo polinomial en gráficos planar?
Por lo que yo sé:
- Max corte en grafos planos
- cuatro colorear grafos planos
- Max conjunto independiente en cúbicos grafos planos
esperanza a alguien puede completar esta lista
Creo que esto pertenece a cstheory.se – Alexandru
Mirando su [FAQ] (http://cstheory.stackexchange.com/faq), creo que cstheory.se probablemente cerraría esto. –
Cerré esto porque parece ser una pregunta de "Lista de X", pero estoy reabriendo con la esperanza de que haya un recurso con la respuesta. Si otros sienten que no hay una sola respuesta correcta, pueden votar para cerrar. –