Dominação Vetorial na Família dos Grafos Split-Indiferença
Resumo
Este trabalho apresenta um algoritmo polinomial capaz de solucionar o Problema da Dominação Vetorial para grafos Split-Indiferença. O método proposto decorre de duas características inerentes a esta classe de grafos: a limitação do número de vértices simpliciais e a divisão em no máximo três cliques maximais.
Referências
Bertossi, A. A. (1984). Dominating sets for split and bipartite graphs. Information Processing Letters, 19(1):37–40.
Booth, K. S. (1980). Dominating Sets in Chordal Graphs. Technical report, University of Waterloo.
Garey, M. R. and Johnson, D. S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.
Ortiz, C. Z., Maculan, N., and Szwarcfiter, J. L. (1998). Characterizing and edge-colouring split-indifference graphs. Discrete Applied Mathematics, 82(1-3):209–217.
Booth, K. S. (1980). Dominating Sets in Chordal Graphs. Technical report, University of Waterloo.
Garey, M. R. and Johnson, D. S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.
Ortiz, C. Z., Maculan, N., and Szwarcfiter, J. L. (1998). Characterizing and edge-colouring split-indifference graphs. Discrete Applied Mathematics, 82(1-3):209–217.
Publicado
26/07/2018
Como Citar
MAFORT, Rodrigo Lamblet; PROTTI, Fábio.
Dominação Vetorial na Família dos Grafos Split-Indiferença. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 9-12.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3139.
