PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1997 | 17 | 2 | 259-269
Tytuł artykułu

Spanning trees with many or few colors in edge-colored graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
17
Numer
2
Strony
259-269
Opis fizyczny
Daty
wydano
1997
otrzymano
1995-11-23
poprawiono
1997-01-30
Twórcy
  • 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
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.