Aspectos de complexidade parametrizada e problemas análogos em problemas de lista coloração de grafos e suas variações
Resumo
Lista-coloração é uma generalização do problema clássico de coloração de vértices em grafos. Tal problema possui algumas variações, dentre elas a coloração. Neste trabalho, uma redutibilidade do problema da lista coloração para a coloração e pré-coloração estendida é apresentada, para melhor se prover uma análise da coloração sob o enfoque da complexidade parametrizada, onde a mesma é FPT quando parametrizada pela cobertura de vértices e listas de cores. É apresentada também a prova de corretude de um algoritmo polinomial, dado na literatura, para coloração em grafos bipartidos completos.
Palavras-chave:
algoritmos, complexidade parametrizada, grafo bipartido, prova de polinomialidade
Referências
Bondy, A. and Murty, U. S. R. (2011). Graph Theory. Graduate Texts in Mathematics. Springer London.
Centeno, C. C. (2012). A convexidade P3 para grafos não direcionados. PhD thesis, UFRJ.
Harari, F. and Holzmann, C. (1974). Line graphs of bipartiti graphs. 1:19–22.
Harary, F., Nieminen, J., et al. (1981). Convexity in graphs. Journal of Differential Geometry, 16(2):185–190.
Maffray, F. and Reed, B. (1999). A description of claw-free perfect graphs. Journal of Combinatorial Theory, 75:134–156.
Moon, J. W. (1972). Embedding tournaments in simple tournaments. Discrete Mathematics, 2(4):389 – 395.
Pelayo, I. M. (2013). Geodesic Convexity in Graphs. SpringerBriefs in Mathematics. Springer New York.
Santhakumaran, A. and John, J. (2007). Edge geodetic number of a graph. Journal of Discrete Mathematical Sciences Cryptography, 3.
Soares, P. R. (2008). Um estudo das estruturas de grafos sem garras. Master’s thesis, UFRJ.
Yannakakis, M. and Gavril, F. (1980). Edge dominating sets in graphs. SIAM Journal on Applied Mathematics, 38(3):364–372.
Centeno, C. C. (2012). A convexidade P3 para grafos não direcionados. PhD thesis, UFRJ.
Harari, F. and Holzmann, C. (1974). Line graphs of bipartiti graphs. 1:19–22.
Harary, F., Nieminen, J., et al. (1981). Convexity in graphs. Journal of Differential Geometry, 16(2):185–190.
Maffray, F. and Reed, B. (1999). A description of claw-free perfect graphs. Journal of Combinatorial Theory, 75:134–156.
Moon, J. W. (1972). Embedding tournaments in simple tournaments. Discrete Mathematics, 2(4):389 – 395.
Pelayo, I. M. (2013). Geodesic Convexity in Graphs. SpringerBriefs in Mathematics. Springer New York.
Santhakumaran, A. and John, J. (2007). Edge geodetic number of a graph. Journal of Discrete Mathematical Sciences Cryptography, 3.
Soares, P. R. (2008). Um estudo das estruturas de grafos sem garras. Master’s thesis, UFRJ.
Yannakakis, M. and Gavril, F. (1980). Edge dominating sets in graphs. SIAM Journal on Applied Mathematics, 38(3):364–372.
Publicado
02/07/2019
Como Citar
GAMA, Simone; DE FREITAS, Rosiane; SOUZA, Ueverton .
Aspectos de complexidade parametrizada e problemas análogos em problemas de lista coloração de grafos e suas variações. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 4. , 2019, Belém.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2019.6402.
