A simple algorithm for edge-coloring bipartite multigraphs

DOI10.1016/S0020-0190(02)00446-5zbMath1173.68594OpenAlexW2008217702WikidataQ56390588 ScholiaQ56390588MaRDI QIDQ1007547

Noga Alon

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00446-5

zbMATH Keywords

edge-coloringgraph algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (10)

Space-Efficient Euler Partition and Bipartite Edge Coloring ⋮ Space-efficient Euler partition and bipartite edge coloring ⋮ Energy efficient monitoring in sensor networks ⋮ Arbitrary-size permutation networks using arbitrary-radix switches ⋮ Decomposing Random Permutations into Order-Isomorphic Subpermutations ⋮ Restricted assignment scheduling with resource constraints ⋮ Colorful strips ⋮ Subset matching and edge coloring in bipartite graphs ⋮ New linear-time algorithms for edge-coloring planar graphs ⋮ Energy Efficient Monitoring in Sensor Networks

Cites Work

• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• A simple matching algorithm for regular bipartite graphs.
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• On Edge Coloring Bipartite Graphs
• Using euler partitions to edge color bipartite multigraphs
• Bipartite Edge Coloring in $O(\Delta m)$ Time

This page was built for publication: A simple algorithm for edge-coloring bipartite multigraphs