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)

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

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)