Minimum multiplicity edge coloring via orientation

DOI10.1016/J.DAM.2018.03.078MaRDI QIDQ1671364zbMATH OpenOpenAlexWikidataFDO

Authors Evangelos Bampas, Christina Karousatou, Aris Pagourtzis, Katerina Potika

Publication date 6 September 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2018.03.078

zbMATH Keywords

approximation algorithmscolor multiplicityedge coloringedge orientationoptical networkspath multicoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Fast edge colorings with fixed number of colors to minimize imbalance
• Fast Edge Colorings with Fixed Number of Colors to Minimize Imbalance
• scientific article; zbMATH DE number 1947051
• An asymptotic approximation scheme for multigraph edge coloring
• Approximation Algorithms for Maximum Edge Coloring Problem

Cites work

• A fast parallel algorithm for routing in permutation networks
• Computer science today. Recent trends and developments
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Link scheduling in wireless sensor networks: distributed edge-coloring revisited
• Minimizing maximum fiber requirement in optical networks
• NP completeness of finding the chromatic index of regular graphs
• Resource allocation problems in multifiber WDM tree networks.
• Routing and path multicoloring
• Routing and wavelength assignment in multifiber WDM networks with non-uniform fiber cost
• Scheduling File Transfers
• Selfish resource allocation in optical networks
• The complexity of path coloring and call scheduling
• The edge intersection graphs of paths in a tree
• The NP-Completeness of Edge-Coloring
• Using euler partitions to edge color bipartite multigraphs

Cited in

(1)

• Minimum number of palettes in edge colorings

This page was built for publication: Minimum multiplicity edge coloring via orientation

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