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

DOI10.1016/0196-6774(86)90039-8zbMATH Open0594.68041OpenAlexW2140029748MaRDI QIDQ3725544FDOQ3725544

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

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

zbMATH Keywords

graph algorithmedge coloring

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• An asymptotic approximation scheme for multigraph edge coloring
• Title not available (Why is that?)
• Polynomial time complexity of edge colouring graphs with bounded colour classes
• Title not available (Why is that?)
• Improving a family of approximation algorithms to edge color multigraphs
• 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
• Using the minimum maximum flow degree to approximate the flow coloring problem
• On a local protocol for concurrent file transfers
• 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)