Improving a family of approximation algorithms to edge color multigraphs

DOI10.1016/S0020-0190(98)00138-0zbMATH Open1339.68313OpenAlexW2020972089MaRDI QIDQ293395FDOQ293395

Authors Alberto Caprara, Romeo Rizzi 

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098001380?np=y

zbMATH Keywords

matchingapproximation algorithmedge coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• A better than “best possible” algorithm to edge color multigraphs
• An asymptotic approximation scheme for multigraph edge coloring
• An asymptotic approximation scheme for multigraph edge coloring
• scientific article; zbMATH DE number 3889546
• Experimental and Efficient Algorithms

Cites Work

• scientific article; zbMATH DE number 3654142 (Why is no real title available?)
• scientific article; zbMATH DE number 795216 (Why is no real title available?)
• A better than “best possible” algorithm to edge color multigraphs
• Fractional covers for forests and matchings
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On edge-colorings of graphs.
• On the $1.1$ Edge-Coloring of Multigraphs
• The NP-Completeness of Edge-Coloring

Cited In (9)

• An asymptotic approximation scheme for multigraph edge coloring
• Improving the performance guarantee for approximate graph coloring
• A better than “best possible” algorithm to edge color multigraphs
• Densities, matchings, and fractional edge-colorings
• An asymptotic approximation scheme for multigraph edge coloring
• Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs
• Approximating the chromatic index of multigraphs
• On hitting all maximum cliques with an independent set
• An upper bound for the chromatic number of line graphs

This page was built for publication: Improving a family of approximation algorithms to edge color multigraphs

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