Wyszukiwarka
Abstrakt
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.
Cytowania
-
1 7
CrossRef
-
0
Web of Science
-
2 0
Scopus
Cytuj jako
Pełna treść
pobierz publikację
pobrano 26 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2009.04.002
- Licencja
- Copyright (2009 Elsevier B.V)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
DISCRETE APPLIED MATHEMATICS
nr 157,
strony 3593 - 3600,
ISSN: 0166-218X - Język:
- angielski
- Rok wydania:
- 2009
- Opis bibliograficzny:
- Kosowski A.: Approximating the maximum 2- and 3-edge-colorable subgraph problems// DISCRETE APPLIED MATHEMATICS. -Vol. 157, nr. iss. 17, October. (2009), s.3593-3600
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2009.04.002
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 108 razy