On Edge Coloring Bipartite Graphs

DOI10.1137/0211043zbMath0486.68062OpenAlexW2170198451WikidataQ56390631 ScholiaQ56390631MaRDI QIDQ3947136

John E. Hopcrofts, Richard John Cole

Publication date: 1982

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6283

zbMATH Keywords

multigraphpartitionmatchingminimal edge coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (27)

An algorithm for improved delay-scaling in input-queued switches ⋮ Space-Efficient Euler Partition and Bipartite Edge Coloring ⋮ Space-efficient Euler partition and bipartite edge coloring ⋮ Approximate constrained bipartite edge coloring ⋮ Graph optimization approaches for minimal rerouting in symmetric three stage Clos networks ⋮ Solving fundamental problems on sparse-meshes ⋮ A complexity analysis and an algorithmic approach to student sectioning in existing timetables ⋮ Data transfers in networks ⋮ A heuristic for decomposing traffic matrices in TDMA satellite communication ⋮ Minimizing the total completion time in a unit-time open shop with release times ⋮ The complexity of scheduling independent two-processor tasks on dedicated processors ⋮ Open shop problem with zero-one time operations and integer release date/deadline intervals ⋮ A linear time algorithm for edge coloring of binomial trees ⋮ Edge coloring graphs with large minimum degree ⋮ Arbitrary-size permutation networks using arbitrary-radix switches ⋮ A Markov chain on the solution space of edge colorings of bipartite graphs ⋮ Multicolor routing in the undirected hypercube ⋮ Some results concerning the complexity of restricted colorings of graphs ⋮ An implicit data structure for searching a multikey table in logarithmic time ⋮ A note on 3D orthogonal graph drawing ⋮ Latin squares with bounded size of row prefix intersections ⋮ Edge coloring of bipartite graphs with constraints ⋮ A simple algorithm for edge-coloring bipartite multigraphs ⋮ A simple matching algorithm for regular bipartite graphs. ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Interval edge coloring of a graph with forbidden colors ⋮ Routing and path multicoloring

This page was built for publication: On Edge Coloring Bipartite Graphs