Super-colored paths in digraphs
Resumo
We work in an Anthropology application where it is desired to enumerate colored rings (structures that look like cycles) present in kinship net-works. For this goal, we came across the following question: for all vertex v of a vertex-colored digraph, how many colors (in maximum) a path starting in v can have? The answer for this question would help us to enumerate the colored rings since we would know how many colors a ring evolving some vertices could have, in maximum. Here, we call a path as v-super-colored if it starts in vertex v and it has the maximum amount of colors among all paths starting in v. We show that the problem to find the number of colors of v-super-colored paths for all v is NP-hard when the input digraph is general. We describe a simple algorithm which demonstrates that the problem is tractable if the input digraphis acyclic and the number of colors is small.
Referências
Chartrand, G., Johns, G. L., McKeon, K. A., and Zhang, P. (2008). Rainbow connectionin graphs.Mathematica Bohemica, 133(1):85–98.
Cowen, L., Goddard, W., and Jesurum, C. E. (1997). Defective coloring revisited.Journalof Graph Theory, 24(3):205–219.
Hamberger, K., Houseman, M., Daillant, I., White, D. R., and Barry, L. (2004). Matri-monial ring structures.Math ́ematiques et sciences humaines. Mathematics and socialsciences, 168:83–119.
Poz, J. d. and Silva, M. F. d. (2009). Maqpar: a homemade tool for the study of kinshipnetworks.Vibrant, 6(2):29–51.
