A better than “best possible” algorithm to edge color multigraphs

DOI10.1016/0196-6774(86)90039-8zbMath0594.68041OpenAlexW2140029748MaRDI QIDQ3725544

Dorit S. Hochbaum, David B. Shmoys, Takao Nishizeki

Publication date: 1986

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(86)90039-8

zbMATH Keywords

graph algorithmedge coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Related Items (11)

Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem ⋮ The linzertorte problem, or a unified approach to painting, baking and weaving ⋮ Improving a family of approximation algorithms to edge color multigraphs ⋮ Using the minimum maximum flow degree to approximate the flow coloring problem ⋮ Approximating the chromatic index of multigraphs ⋮ Graph edge coloring: a survey ⋮ On a local protocol for concurrent file transfers ⋮ Analysis of approximate algorithms for edge-coloring bipartite graphs ⋮ Vizing's coloring algorithm and the fan number ⋮ On the fg-coloring of graphs ⋮ Routing and path multicoloring

This page was built for publication: A better than “best possible” algorithm to edge color multigraphs