On Edge Coloring Bipartite Graphs

DOI10.1137/0211043MaRDI QIDQ3947136zbMATH OpenOpenAlexWikidataFDO

Authors John Hopcroft, Richard 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

multigraphmatchingpartitionminimal edge coloring

Mathematics Subject Classification ID

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

Cited in

(28)

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

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

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