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

DOI10.1016/J.JDA.2007.08.002zbMath1146.68071OpenAlexW2099431183MaRDI QIDQ935838

Ruka Tanahashi, Zhi-Zhong Chen, Lusheng Wang

Publication date: 8 August 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2007.08.002

zbMATH Keywords

randomizationapproximation algorithmsderandomizationmaximum \(b\)-matchingmaximum edge \(t\)-coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement ⋮ Approximating the maximum 2- and 3-edge-colorable subgraph problems ⋮ Approximating maximum edge 2-coloring in simple graphs via local improvement ⋮ Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

Cites Work

• An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs
• Path factors in cubic graphs
• Complexity of Recognizing Equal Unions in Families of Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An improved approximation algorithm for maximum edge 2-coloring in simple graphs