Algorithms for Edge Coloring Bipartite Graphs and Multigraphs

DOI10.1137/0211009zbMath0486.05034OpenAlexW2120729889MaRDI QIDQ3946187

Oded Kariv, Harold N. Gabow

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1137/0211009

zbMATH Keywords

open shop schedulingEuler partitionmaximum cardinality matching problemsminimum edge colorings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items (28)

Space-Efficient Euler Partition and Bipartite Edge Coloring ⋮ Efficient Vertex- and Edge-Coloring of Outerplanar Graphs ⋮ A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job ⋮ Space-efficient Euler partition and bipartite edge coloring ⋮ Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications ⋮ Approximate constrained bipartite edge coloring ⋮ Distributed edge coloration for bipartite networks ⋮ A self-stabilizing \((\Delta +4)\)-edge-coloring algorithm for planar graphs in anonymous uniform systems ⋮ Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches ⋮ Shop scheduling problems with multiprocessor tasks on dedicated processors ⋮ Parallel O(log n) time edge-colouring of trees and Halin graphs ⋮ Open shop problems with unit time operations ⋮ A complete 4-parametric complexity classification of short shop scheduling problems ⋮ Maximum matching in regular and almost regular graphs ⋮ Optimally edge-colouring outerplanar graphs is in NC ⋮ Distributed algorithms for maximum cliques ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Subset matching and edge coloring in bipartite graphs ⋮ Path colorings in bipartite graphs ⋮ An integer programming approach to the time slot assignment problem in SS/TDMA systems with intersatellite links ⋮ On a conjecture for the university timetabling problem ⋮ Edge coloring of bipartite graphs with constraints ⋮ Complete Complexity Classification of Short Shop Scheduling ⋮ Combinatorial algorithms for data migration to minimize average completion time ⋮ A linear time approximation algorithm for permutation flow shop scheduling ⋮ A generalized class-teacher model for some timetabling problems ⋮ Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems)

This page was built for publication: Algorithms for Edge Coloring Bipartite Graphs and Multigraphs