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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)
Cites Work
- The NP-Completeness of Edge-Coloring
- Title not available (Why is that?)
- Fractional covers for forests and matchings
- On the $1.1$ Edge-Coloring of Multigraphs
- A better than “best possible” algorithm to edge color multigraphs
- On edge-colorings of graphs.
- On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
- Title not available (Why is that?)
Cited In (8)
- 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
- Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs
- Approximating the chromatic index of multigraphs
- Densities, Matchings, and Fractional Edge-Colorings
- 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)
