An improved approximation algorithm for maximum edge 2-coloring in simple graphs

Zhi-Zhong Chen; Ruka Tanahashi; Lusheng Wang

doi:10.1016/j.jda.2007.08.002

An improved approximation algorithm for maximum edge 2-coloring in simple graphs

Zhi-Zhong Chen
, Ruka Tanahashi
, Lusheng Wang

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 22 - Publication in policy or professional journal

8 Citations (Scopus)

Abstract

We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of frac(468, 575). This improves on the previous best (trivial) ratio of frac(4, 5). © 2007 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	205-215
Journal	Journal of Discrete Algorithms
Volume	6
Issue number	2
DOIs	https://doi.org/10.1016/j.jda.2007.08.002
Publication status	Published - Jun 2008

Research Keywords

Approximation algorithms
Derandomization
Maximum b-matching
Maximum edge t-coloring
Randomization

Access Output

10.1016/j.jda.2007.08.002Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{81d2b9ffae3e4eae8415a3449b026ef2,

title = "An improved approximation algorithm for maximum edge 2-coloring in simple graphs",

abstract = "We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of frac(468, 575). This improves on the previous best (trivial) ratio of frac(4, 5). {\textcopyright} 2007 Elsevier B.V. All rights reserved.",

keywords = "Approximation algorithms, Derandomization, Maximum b-matching, Maximum edge t-coloring, Randomization",

author = "Zhi-Zhong Chen and Ruka Tanahashi and Lusheng Wang",

year = "2008",

month = jun,

doi = "10.1016/j.jda.2007.08.002",

language = "English",

volume = "6",

pages = "205--215",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - An improved approximation algorithm for maximum edge 2-coloring in simple graphs

AU - Chen, Zhi-Zhong

AU - Tanahashi, Ruka

AU - Wang, Lusheng

PY - 2008/6

Y1 - 2008/6

N2 - We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of frac(468, 575). This improves on the previous best (trivial) ratio of frac(4, 5). © 2007 Elsevier B.V. All rights reserved.

AB - We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of frac(468, 575). This improves on the previous best (trivial) ratio of frac(4, 5). © 2007 Elsevier B.V. All rights reserved.

KW - Approximation algorithms

KW - Derandomization

KW - Maximum b-matching

KW - Maximum edge t-coloring

KW - Randomization

UR - https://www.scopus.com/pages/publications/42249107825

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-42249107825&origin=recordpage

U2 - 10.1016/j.jda.2007.08.002

DO - 10.1016/j.jda.2007.08.002

M3 - RGC 22 - Publication in policy or professional journal

SN - 1570-8667

VL - 6

SP - 205

EP - 215

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

IS - 2

ER -

An improved approximation algorithm for maximum edge 2-coloring in simple graphs

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this