Czasopismo
Tytuł artykułu
Autorzy
Treść / Zawartość
Pełne teksty:
Warianty tytułu
Języki publikacji
Abstrakty
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.
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
259-269
Opis fizyczny
Daty
wydano
1997
otrzymano
1995-11-23
poprawiono
1997-01-30
Twórcy
autor
- Faculty of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands
autor
- Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an, Shaanxi 710072, P.R. China
Bibliografia
- [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan-Elsevier, London-New York, 1976).
- [2] M.R. Garey and D.S. Johnson, Computers and Intractability (Freeman, New York, 1979).
- [3] E.L. Lawler, Combinatorial Optimization, Networks and Matroids (Holt, Rinehart and Winston, New York, 1976).
- [4] D.J.A. Welsh, Matroid Theory (Academic Press, London-New York-San Francisco, 1976).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1053