Primero preguntado en matemáticas . SE sin respuestas.
- Supongamos que tengo un gráfico plano, con una incrustación plana, ¿cómo encuentro la descomposición del árbol?
- ¿Cuál es la descomposición óptima del árbol de una rejilla cuadrada -by- d ? No estoy completamente seguro de cómo definir "óptimo", pero debe distinguir entre la descomposición con una bolsa grande y la descomposición con muchas bolsas grandes.
ds.algorithms
graph-theory
graph-algorithms
treewidth
integer-lattice
Yaroslav Bulatov
fuente
fuente
Para la primera pregunta, está abierto si se puede encontrar la descomposición de un árbol para gráficos planos en tiempo polinómico. El mejor algoritmo de aproximación puede ser el algoritmo RatCatcher de Seymour y Thomas, que calcula el ancho de rama del gráfico plano, por lo que tiene una relación de aproximación de 1.5 por la relación entre ancho de rama y ancho de árbol.
fuente
Si no desea una descomposición óptima del árbol, puede construir una descomposición del árbol calculando separadores de forma recursiva.
fuente