A simple algorithm for edge-coloring bipartite multigraphs

DOI10.1016/S0020-0190(02)00446-5zbMath1173.68594WikidataQ56390588 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-coloring; graph algorithms

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

Related Items

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, Subset matching and edge coloring in bipartite graphs, Energy efficient monitoring in sensor networks, Colorful strips, Space-efficient Euler partition and bipartite edge coloring, Restricted assignment scheduling with resource constraints, New linear-time algorithms for edge-coloring planar graphs

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