En el área matemática de la teoría de grafos , un grafo no tiene huecos pares si no contiene un ciclo inducido con un número par de vértices .
Addario-Berry y col. (2008) demostraron que cada gráfico libre de agujeros pares contiene un vértice bisimplicial , lo que estableció una conjetura de Reed.
Reconocimiento
Conforti y col. (2002b) dio el primer algoritmo de reconocimiento de tiempo polinomial para gráficos sin huecos pares, que se ejecuta enhora. [1] da Silva y Vušković (2008) posteriormente mejoraron esto para. Chang & Lu (2012) y Chang & Lu (2015) mejoraron esto parahora. El algoritmo más conocido actualmente lo dan Lai, Lu & Thorup (2020) que se ejecuta en hora.
Si bien los gráficos sin huecos pares se pueden reconocer en tiempo polinomial, es NP -completo determinar si un gráfico contiene un hueco par que incluye un vértice específico. [2]
Se desconoce si la coloración del gráfico y el problema del conjunto máximo independiente se pueden resolver en tiempo polinómico en gráficos sin huecos pares, o si son NP-completos. Sin embargo, la camarilla máxima se puede encontrar en gráficos sin huecos pares en tiempo polinomial. [3]
Notas
- ^ Conforti y col. (2002b) presentan su algoritmo y afirman que se ejecuta en tiempo polinomial sin dar un análisis explícito. Chudnovsky, Kawarabayashi y Seymour (2004) estiman que se ejecuta en "tiempo sobre. "
- ^ Bienstock (1991)
- ↑ Vušković (2010) .
Referencias
- Addario-Berry, Louigi; Chudnovsky, Maria ; Havet, Frédéric; Reed, Bruce ; Seymour, Paul (2008), "Vértices bisimpliciales en gráficos sin huecos pares", Journal of Combinatorial Theory, Serie B , 98 (6): 1119-1164, doi : 10.1016 / j.jctb.2007.12.006
- Bienstock, Dan (1991), "Sobre la complejidad de las pruebas de agujeros impares y trayectorias impares inducidas", Matemáticas discretas , 90 (1): 85–92, doi : 10.1016 / 0012-365X (91) 90098-M
- Chudnovsky, Maria ; Kawarabayashi, Ken-ichi ; Seymour, Paul (2004), "Detectando agujeros pares", Journal of Graph Theory , 48 (2): 85-111, doi : 10.1002 / jgt.20040
- Conforti, Michele; Cornuéjols, Gérard ; Kapoor, Ajai; Vušković, Kristina (enero de 2002a), "Gráficos sin agujeros pares, parte I: teorema de descomposición" (PDF) , Journal of Graph Theory , 39 (1): 6–49, doi : 10.1002 / jgt.10006
- Conforti, Michele; Cornuéjols, Gérard ; Kapoor, Ajai; Vušković, Kristina (agosto de 2002b), "Gráficos sin agujeros pares, parte II: algoritmo de reconocimiento" (PDF) , Journal of Graph Theory , 40 (4): 238–266, doi : 10.1002 / jgt.10045
- da Silva, Murilo VG; Vušković, Kristina (2008), Descomposición de gráficos sin agujeros pares con cortes en estrella y 2 uniones
- Chang, Hsien-Chih; Lu, Hsueh-I (enero de 2012), "Un algoritmo más rápido para reconocer gráficos sin agujeros pares" , SODA '12: Actas del vigésimo tercer simposio anual ACM-SIAM sobre algoritmos discretos : 1286-1297, doi : 10.1137 /1.9781611973099.101 , ISBN 978-1-61197-210-8
- Chang, Hsien-Chih; Lu, Hsueh-I (julio de 2015), "Un algoritmo más rápido para reconocer gráficos sin agujeros pares", Journal of Combinatorial Theory, Serie B , 113 : 141-161, arXiv : 1311.0358 , doi : 10.1016 / j.jctb. 2015.02.001 , S2CID 1744497
- Vušković, Kristina (2010), "Gráficos sin agujeros pares: una encuesta" (PDF) , Applicable Analysis and Discrete Mathematics , 4 (2): 219–240, doi : 10.2298 / AADM100812027V , JSTOR 43666110 , MR 2724633
- Lai, Kai-Yuan; Lu, Hsueh-I; Thorup, Mikkel (junio de 2020), "Three-in-a-Tree in Near Linear Time" , STOC 2020: Actas del 52º Simposio Anual de ACM SIGACT sobre Teoría de la Computación : 1279–1292, arXiv : 1909.07446 , doi : 10.1145 / 3357713 , ISBN 9781450369794
enlaces externos
- "Gráficos sin agujeros pares" , sistema de información sobre clases de gráficos y sus inclusiones