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

DOI10.1016/0196-6774(86)90039-8MaRDI QIDQ3725544zbMATH OpenOpenAlexFDO

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

Recommendations

• scientific article; zbMATH DE number 3889546
• Improving a family of approximation algorithms to edge color multigraphs
• An asymptotic approximation scheme for multigraph edge coloring
• An asymptotic approximation scheme for multigraph edge coloring
• On the $1.1$ Edge-Coloring of Multigraphs

Cited in

(29)

• On the $1.1$ Edge-Coloring of Multigraphs
• New Bounds for the Nearly Equitable Edge Coloring Problem
• Routing and path multicoloring
• A Linear Algorithm for Edge-Coloring Series–Parallel Multigraphs
• Improved edge-coloring with three colors
• Densities, matchings, and fractional edge-colorings
• scientific article; zbMATH DE number 3889546 (Why is no real title available?)
• An asymptotic approximation scheme for multigraph edge coloring
• scientific article; zbMATH DE number 1998816 (Why is no real title available?)
• Polynomial time complexity of edge colouring graphs with bounded colour classes
• Improving a family of approximation algorithms to edge color multigraphs
• scientific article; zbMATH DE number 1947051 (Why is no real title available?)
• A simple and fast heuristic algorithm for edge-coloring of graphs
• Vizing's coloring algorithm and the fan number
• Improved Edge-Coloring with Three Colors
• Efficiently list‐edge coloring multigraphs asymptotically optimally
• Experimental and Efficient Algorithms
• Approximating the chromatic index of multigraphs
• On the fg-coloring of graphs
• On a local protocol for concurrent file transfers
• Using the minimum maximum flow degree to approximate the flow coloring problem
• Approximating the maximum 3- and 4-edge-colorable subgraph (extended abstract)
• On coloring problems for two-season multigraphs
• Graph edge coloring: a survey
• Edge-coloring of multigraphs
• Beyond the Vizing's bound for at most seven colors
• 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
• Analysis of approximate algorithms for edge-coloring bipartite graphs

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

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