A simple algorithm for edge-coloring bipartite multigraphs

DOI10.1016/S0020-0190(02)00446-5MaRDI QIDQ1007547zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Cites work

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

Cited in

(12)

• Space-efficient Euler partition and bipartite edge coloring
• Restricted assignment scheduling with resource constraints
• New linear-time algorithms for edge-coloring planar graphs
• Subset matching and edge coloring in bipartite graphs
• 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
• Energy efficient monitoring in sensor networks
• The power of multi-step Vizing chains
• Colorful strips
• Vizing's theorem in near-linear time

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

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