Approximating maximum edge 2-coloring in simple graphs

DOI10.1016/J.DAM.2010.08.010MaRDI QIDQ608271zbMATHOpenAlexFDO

Authors Zhi-Zhong Chen, Sayuri Konno, Yuki Matsushita

Publication date 25 November 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.08.010

zbMATH Keywords

approximation algorithmsgraph algorithmsNP-hardnessedge coloring

Mathematics Subject Classification ID

Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Approximating maximum edge 2-coloring in simple graphs
• An improved approximation algorithm for maximum edge 2-coloring in simple graphs
• An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs
• Approximating maximum edge 2-coloring in simple graphs via local improvement
• Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 1947051 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• Algorithmic aspects in information and management. Third international conference, AAIM 2007, Portland, OR, USA, June 6--8, 2007. Proceedings.
• Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• Complexity of Recognizing Equal Unions in Families of Sets
• Packing \([1, \Delta ]\)-factors in graphs of small degree
• Path factors in cubic graphs

Cited in

(12)

• \(M_2\)-edge coloring and maximum matching of graphs
• Approximating maximum edge 2-coloring in simple graphs
• An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs
• Online edge coloring of paths and trees with a fixed number of colors
• Approximating maximum edge 2-coloring in simple graphs via local improvement
• An approximation algorithm for covering vertices by \(4^+\)-paths
• Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement
• Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• An improved approximation algorithm for maximum edge 2-coloring in simple graphs
• Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture
• Online Dual Edge Coloring of Paths and Trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q608271)