EUVIMEDEUVIMED entdecken
Crossref

Edge Coloring of Multigraphs With Very High Multiplicities

Jan De Neve, Didier Colle, Wouter Tavernier, Mario Pickavet

Networks · 2026-09 · 88 (2) · 275-290

DOI: 10.1002/net.70054 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Networks, online erschienen am 15.06.2026. Verfasst von Jan De Neve und 3 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben. Gefördert von: Bijzonder Onderzoeksfonds UGent.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Vizing's generalized theorem states that any multigraph with maximum degree and maximum multiplicity has an edge coloring with at most colors. The runtime of Vizing's algorithm, which can find such a coloring, scales quadratically with . This is an important drawback for multigraphs arising from applications like photonic networks, where edge degrees and multiplicities can be very high. In this work, we propose a new edge coloring algorithm for multigraphs, which scales linearly with . To the best of our knowledge, no existing edge coloring algorithm, using so few colors, scales less than quadratically with . We describe one algorithm that finds a near‐optimal coloring and another algorithm that finds an optimal coloring with and worst‐case time complexity, respectively. We verify the working mechanisms as well as the performance of these algorithms, both for purely random test inputs and for synthetic test inputs whose structure is based on real applications.

Förderung

  • Bijzonder Onderzoeksfonds UGent

Zitieren

APA

Neve, J. D., Colle, D., Tavernier, W., & Pickavet, M. (2026). Edge Coloring of Multigraphs With Very High Multiplicities. Networks, 88(2), 275-290. https://doi.org/10.1002/net.70054

Vancouver

Neve JD, Colle D, Tavernier W, Pickavet M. Edge Coloring of Multigraphs With Very High Multiplicities. Networks. 2026;88(2):275-290. doi:10.1002/net.70054

BibTeX
@article{Neve2026,
  author = {Neve, Jan De and Colle, Didier and Tavernier, Wouter and Pickavet, Mario},
  title = {Edge Coloring of Multigraphs With Very High Multiplicities},
  journal = {Networks},
  year = {2026},
  volume = {88},
  number = {2},
  pages = {275--290},
  doi = {10.1002/net.70054}
}
Kostenlos starten →