Approximating maximum edge 2-coloring in simple graphs via local improvement

DOI10.1016/j.tcs.2009.07.008zbMath1187.68338OpenAlexW2759053159MaRDI QIDQ1035687

Zhi-Zhong Chen, Ruka Tanahashi

Publication date: 4 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.008

zbMATH Keywords

edge coloringgraph algorithmsapproximation algorithmsNP-hardness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved approximation algorithm for maximum edge 2-coloring in simple graphs
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• Packing \([1, \Delta \)-factors in graphs of small degree]
• Path factors in cubic graphs
• Complexity of Recognizing Equal Unions in Families of Sets

This page was built for publication: Approximating maximum edge 2-coloring in simple graphs via local improvement