Hispanopedia WikiEl problema de completitud hamiltoniana es encontrar el número mínimo de aristas que se deben agregar a un grafo para hacerlo hamiltoniano .
El problema es claramente NP-completo en el caso general (ya que su solución da una respuesta al problema NP-completo de determinar si un grafo dado tiene un ciclo hamiltoniano ). El problema de decisión asociado de determinar si se pueden agregar K aristas a un grafo dado para producir un grafo hamiltoniano es NP-completo.
Además, la completitud hamiltoniana pertenece a la clase de complejidad APX , es decir, es poco probable que existan algoritmos de aproximación de razón constante eficientes para este problema. [1]
El problema puede resolverse en tiempo polinomial para ciertas clases de gráficos, incluidos los gráficos serie-paralelos [2] y sus subgráficos [3] , que incluyen gráficos exteriores-planares , así como para un gráfico lineal de un árbol [4] [5] o un gráfico de cactus . [6]
Gamarnik et al. utilizan un algoritmo de tiempo lineal para resolver el problema en árboles para estudiar el número asintótico de aristas que deben agregarse a los gráficos aleatorios dispersos para hacerlos hamiltonianos. [7]
Referencias
- ^ Wu, QS; Lu, Chin Lung; Lee, Richard CT (2000), "Un algoritmo aproximado para el problema de compleción de ruta hamiltoniana ponderada en un árbol", en Lee, DT; Teng, Shang-Hua (eds.), Algorithms and Computation, 11.ª Conferencia Internacional, ISAAC 2000, Taipei, Taiwán, 18-20 de diciembre de 2000, Actas , Lecture Notes in Computer Science, vol. 1969, Springer, págs. 156-167, doi :10.1007/3-540-40996-3_14, ISBN 978-3-540-41255-7
- ^ Takamizawa, K.; Nishizeki, T .; Saito, N. (1982), "Computabilidad en tiempo lineal de problemas combinatorios en grafos serie-paralelos", Journal of the ACM , 29 (3): 623–641, doi : 10.1145/322326.322328 , S2CID 16082154.
- ^ Korneyenko, NM (1994), "Algoritmos combinatorios en una clase de grafos", Discrete Applied Mathematics , 54 (2–3): 215–217, doi : 10.1016/0166-218X(94)90022-1 , MR 1300246
- ^ Raychaudhuri, Arundhati (1995), "El número de intervalo total de un árbol y el número de completitud hamiltoniana de su gráfico lineal", Information Processing Letters , 56 (6): 299–306, doi :10.1016/0020-0190(95)00163-8, MR 1366337
- ^ Agnetis, A.; Detti, P.; Meloni, C.; Pacciarelli, D. (2001), "Un algoritmo lineal para el número de completitud hamiltoniano del gráfico lineal de un árbol", Information Processing Letters , 79 (1): 17–24, doi :10.1016/S0020-0190(00)00164-2, MR 1832044
- ^ Detti, Paolo; Meloni, Carlo (2004), "Un algoritmo lineal para el número de completitud hamiltoniano del gráfico lineal de un cactus", Discrete Applied Mathematics , 136 (2–3): 197–215, doi :10.1016/S0166-218X(03)00441-4, MR 2045212
- ^ Gamarnik, David; Sviridenko, Maxim (2005), "Completaciones hamiltonianas de grafos aleatorios dispersos" (PDF) , Discrete Applied Mathematics , 152 (1–3): 139–158, doi :10.1016/j.dam.2005.05.001, MR 2174199