%A Franco, Álvaro J. P.
%A Vendramin, Marcelo E.
%D 2021
%T Super-colored paths in digraphs
%K
%X 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.
%U https://sol.sbc.org.br/index.php/etc/article/view/16389
%J Anais do Encontro de Teoria da Computação (ETC)
%0 Journal Article
%R 10.5753/etc.2021.16389
%P 94-97%@ 2595-6116
%8 2021-07-18