- Tytuł:
- Spanning trees with many or few colors in edge-colored graphs
- Autorzy:
-
Broersma, Hajo
Li, Xueliang - Powiązania:
- https://bibliotekanauki.pl/articles/971955.pdf
- Data publikacji:
- 1997
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
edge-coloring
spanning tree
matroid (intersection)
complexity
NP-complete
NP-hard
polynomial algorithm
(minimum) dominating set - Opis:
- Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 1997, 17, 2; 259-269
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł