Tropical matchings in vertex-colored graphs

Cohen, J. and Manoussakis, Y. and Phong, H. P. and Tuza, Zsolt (2017) Tropical matchings in vertex-colored graphs. ELECTRONIC NOTES IN DISCRETE MATHEMATICS, 62. pp. 219-224. ISSN 1571-0653

Text 1-s2.0-S1571065317302779-main.pdf Restricted to Registered users only Download (195kB) | Request a copy

Abstract

A subgraph of a vertex-colored graph is said to be tropical whenever it contains all colors of the original graph. In this work we study 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),O(nm)}. We also provide a polynomial algorithm of time O(nmn) for finding, if any, a minimum tropical matching in vertex-colored graphs. © 2017 Elsevier B.V.

Actions (login required)

Edit Item