Edge Coloring of Multigraphs With Very High Multiplicities
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.
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}
}
EUVIMED