| Tartalom: |
http://real.mtak.hu/74270/ |
| Archívum: |
MTA Könyvtár |
| Gyűjtemény: |
Status = Published
Type = Article
|
| Cím: |
Tropical matchings in vertex-colored graphs
|
| Létrehozó: |
Cohen, J.
Manoussakis, Y.
Phong, H. P.
Tuza, Zsolt
|
| Kiadó: |
Elsevier
|
| Dátum: |
2017
|
| Téma: |
QA166-QA166.245 Graphs theory / grĂĄfelmĂŠlet
|
| Tartalmi leírás: |
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.
|
| Nyelv: |
magyar
|
| Típus: |
Article
PeerReviewed
info:eu-repo/semantics/article
|
| Formátum: |
text
|
| Azonosító: |
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
|
| Kapcsolat: |
https://doi.org/10.1016/j.endm.2017.10.038
MTMT:3332992; doi:10.1016/j.endm.2017.10.038
|
