Using euler partitions to edge color bipartite multigraphs

DOI10.1007/BF00998632zbMath0411.05039WikidataQ29028581 ScholiaQ29028581MaRDI QIDQ4198790

Harold N. Gabow

Publication date: 1976

Published in: International Journal of Computer & Information Sciences (Search for Journal in Brave)

zbMATH Keywords

algorithm; edge coloring; bipartite multigraph; Euler partition matching

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

Related Items

Short Proof of Galvin's Theorem on the List-chromatic Index of a Bipartite Multigraph, Space-Efficient Euler Partition and Bipartite Edge Coloring, The complexity of arc-colorings for directed hypergraphs, Edge coloring of bipartite graphs with constraints, The complexity of arc-colorings for directed hypergraphs, Linear algorithms for edge-coloring trees and unicyclic graphs, A simple algorithm for edge-coloring bipartite multigraphs, Combinatorial analysis (nonnegative matrices, algorithmic problems), An implicit data structure for searching a multikey table in logarithmic time, A parallel algorithm for edge-coloring of graphs with edge-disjoint cycles, A parallel algorithm for approximating the minimum cycle cover, Rearrangeable nonblocking condition for multi-log\(_ 2 N\) multiconnection networks, The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3, Space-efficient Euler partition and bipartite edge coloring, Minimum multiplicity edge coloring via orientation, Path multicoloring in spider graphs with even color multiplicity, A simple matching algorithm for regular bipartite graphs., Approximate constrained bipartite edge coloring, From L. Euler to D. König

Cites Work

• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item