Dla ustalonej wartości parametru k>=2, problem maksymalnego podgrafu krawędziowo k-kolorowalnego polega na wskazaniu k rozłącznych skojarzeń w grafie prostym, a kryterium optymalizacji jest maksymalizacja całkowitej liczby użytych krawędzi. W pracy podano algorytmy 5/6- i 4/5-przybliżone odpowiednio dla przypadków k=2 i k=3, poprawiając wyniki znane z literatury.
Authors
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1016/j.dam.2009.04.002
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2009
