Approximate constrained bipartite edge coloring

DOI10.1016/j.dam.2003.12.006zbMath1055.05045OpenAlexW1506813909MaRDI QIDQ1887041

Ioannis Caragiannis, Pino Persiano, Herve Rivano, Christos Kaklamanis, Afonso G. Ferreira, Stéphane Pérennes

Publication date: 23 November 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2003.12.006

zbMATH Keywords

bipartite graphedge coloringmulticommodity flowsrandomized roundingperfect matchings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• On Edge Coloring Bipartite Graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• Using euler partitions to edge color bipartite multigraphs
• Bipartite Edge Coloring in $O(\Delta m)$ Time
• NP completeness of the edge precoloring extension problem on bipartite graphs
• Constrained bipartite edge coloring with applications to wavelength routing
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An approximation algorithm for circular arc colouring
• Edge coloring of bipartite graphs with constraints

This page was built for publication: Approximate constrained bipartite edge coloring