Search
Abstract
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.
Citations
-
1 7
CrossRef
-
0
Web of Science
-
2 0
Scopus
Cite as
Full text
download paper
downloaded 26 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2009.04.002
- License
- Copyright (2009 Elsevier B.V)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
DISCRETE APPLIED MATHEMATICS
no. 157,
pages 3593 - 3600,
ISSN: 0166-218X - Language:
- English
- Publication year:
- 2009
- Bibliographic description:
- 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:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2009.04.002
- Verified by:
- Gdańsk University of Technology
seen 108 times