Preguntas etiquetadas con treewidth

13
¿Cuál es la definición correcta de

Como dice el título, ¿cuál es la definición correcta de -tree? Hay varios documentos que hablan de k -Los árboles y parcial k -Árboles como definiciones alternativas para gráficos con treewidth acotada, y he visto muchas definiciones aparentemente incorrectas. Por ejemplo, al menos un lugar define...

12
¿El ancho de árbol

Dejemos que kkk sea ​​fijo, y que GGG sea ​​un gráfico (conectado). Si no me equivoco, se deduce del trabajo de Bodlaender [1, Teorema 3.11] que si el ancho de árbol de GGG es aproximadamente de al menos 2k32k32k^3 , entonces GGG contiene una estrella K1,kK1,kK_{1,k} como menor. ¿Podemos hacer que...

10
Relación entre ancho de árbol y número de camarilla

¿Hay algunas clases gráficas agradables para las cuales el ancho del árbol esté limitado por una función del número de camarilla ω ( G ) , es decir, t w ( G ) ≤ f ( ω ( G ) ) ?t w ( G )tw(G)tw(G)ω ( G )ω(G)\omega(G)t w ( G ) ≤ f( ω ( G ) )tw(G)≤f(ω(G))tw(G)\leq f(\omega(G)) Por ejemplo, es un...

10
Clases de gráficos con ancho de árbol superconstante

Hay varias clases interesantes de gráficos con ancho de árbol acotado. Por ejemplo, árboles (ancho de árbol 1), gráficos paralelos en serie (ancho de árbol 2), gráficos de plano externo (ancho de árbol 2), gráficos -outerplanar (ancho de árbol O (k)), gráficos de ancho de rama k (ancho de árbol O...

9
Casos especiales de TSP gráfico

En Graphic TSP , se le proporciona un gráfico no dirigido no ponderado y el objetivo es encontrar un recorrido más corto en que visite cada vértice al menos una vez . Tenga en cuenta que esto no es igual que la búsqueda de un circuito hamiltoniano en . Mis preguntas son:G GGGGGGGGGG ¿Cuál es la...