Skip to Main content Skip to Navigation
Journal articles

Tropical paths in vertex-colored graphs

Abstract : A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the initial graph. In this work we study the problem of finding tropical paths in vertex-colored graphs. There are two versions for this problem: the shortest tropical path problem (STPP), i.e., finding a tropical path with the minimum total weight, and the maximum tropical path problem (MTPP), i.e., finding a path with the maximum number of colors possible. We show that both versions of this problems are NP-hard for directed acyclic graphs, cactus graphs and interval graphs. Moreover, we also provide a fixed parameter algorithm for STPP in general graphs and several polynomial-time algorithms for MTPP in specific graphs, including bipartite chain graphs, threshold graphs, trees, block graphs, and proper interval graphs.
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03508306
Contributor : Frédéric Davesne Connect in order to contact the contributor
Submitted on : Monday, January 3, 2022 - 3:56:44 PM
Last modification on : Wednesday, January 5, 2022 - 3:41:34 AM

Identifiers

Citation

Johanne Cohen, Giuseppe Italiano, Yannis Manoussakis, Nguyen Kim Thang, Hong Phong Pham. Tropical paths in vertex-colored graphs. Journal of Combinatorial Optimization, Springer Verlag, 2021, 42 (3), pp.476--498. ⟨10.1007/s10878-019-00416-y⟩. ⟨hal-03508306⟩

Share

Metrics

Les métriques sont temporairement indisponibles