Approximating maximum edge 2-coloring in simple graphs

DOI10.1007/978-3-642-14355-7_9MaRDI QIDQ3578359zbMATH OpenOpenAlexFDO

Authors Zhi-Zhong Chen, Sayuri Konno, Yuki Matsushita

Publication date 20 July 2010

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14355-7_9

zbMATH Keywords

approximation algorithmsedge coloringgraph algorithmsNP-hardness

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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

Cited in

(8)

• Approximating maximum edge 2-coloring in simple graphs via local improvement
• M₂-edge coloring and maximum matching of graphs
• Parameterized and approximation algorithms for finding two disjoint matchings
• Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement
• An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs
• Approximating maximum edge 2-coloring in simple graphs
• An improved approximation algorithm for maximum edge 2-coloring in simple graphs
• Approximating the maximum 2- and 3-edge-colorable subgraph problems

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 Q3578359)