Approximating the maximum 2- and 3-edge-colorable subgraph problems - Publication - Bridge of Knowledge

Search

Approximating the maximum 2- and 3-edge-colorable subgraph problems

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 5

    CrossRef

  • 0

    Web of Science

  • 1 7

    Scopus

Cite as

Full text

download paper
downloaded 0 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 57 times

Recommended for you

Meta Tags