Download como arquivo ICAL
Seminário de TCCO: Tropical matchings in vertex-colored graphs
Sexta-feira 07 Dezembro 2018, 14:00 - 15:30
Contato: Este endereço de email está sendo protegido de spambots. Você precisa do JavaScript ativado para vê-lo.


In this talk, we focus on an algorithm for finding the maximum matching in a general graph. A matching $M$ in a graph is a set of edges without common vertices. A matching is maximal if no proper superset of $M$ is also a matching. Matching problems have received a lot of attention in different areas. A subgraph of a vertex-colored graph is said to be tropical whenever it contains all colors of the original graph. In this talk, we present the problem of finding, if any, maximum tropical matchings in vertex-colored graphs. We show that this problem is polynomial with complexity $max(O(cm,sqrt{n}m))$. We also provide a polynomial algorithm of time $O(nmsqrt{n})$ for finding, if any, a minimum tropical matching in vertex-colored graphs.

Local IME-USP - Bloco B - Sala 101