Improving a family of approximation algorithms to edge color multigraphs

DOI10.1016/S0020-0190(98)00138-0zbMath1339.68313OpenAlexW2020972089MaRDI QIDQ293395

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

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

Related Items (4)

Approximating the chromatic index of multigraphs ⋮ Densities, Matchings, and Fractional Edge-Colorings ⋮ An upper bound for the chromatic number of line graphs ⋮ On hitting all maximum cliques with an independent set

Cites Work

• Unnamed Item
• Unnamed Item
• Fractional covers for forests and matchings
• On the $1.1$ Edge-Coloring of Multigraphs
• A better than “best possible” algorithm to edge color multigraphs
• The NP-Completeness of Edge-Coloring
• On edge-colorings of graphs.
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte

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