Algorithms for edge coloring bipartite graphs

DOI10.1145/800133.804346MaRDI QIDQ5402556zbMATH OpenOpenAlexFDO

Authors Harold N. Gabow, Oded Kariv

Publication date 14 March 2014

Published in Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/800133.804346

Mathematics Subject Classification ID

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

Recommendations

• Bipartite Edge Coloring in O(\Delta m) Time
• Edge coloring nearly bipartite graphs
• Edge-Coloring Bipartite Graphs
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Finding 1-Factors in Bipartite Regular Graphs and Edge-Coloring Bipartite Graphs

Cited in

(21)

• Combinatorial analysis (nonnegative matrices, algorithmic problems)
• Another look at the degree constrained subgraph problem
• Edge coloring nearly bipartite graphs
• Space-efficient Euler partition and bipartite edge coloring
• A note on polynomial algorithm for cost coloring of bipartite graphs with \(\Delta \leq 4\)
• Hardness results, approximation and exact algorithms for liar's domination problem in graphs
• Distributed edge coloration for bipartite networks
• Solving matching problems efficiently in bipartite graphs
• On the enumeration of bipartite minimum edge colorings
• The edge-cochromatic number of bipartite graph
• Bipartite Edge Coloring in O(\Delta m) Time
• Finding 1-Factors in Bipartite Regular Graphs and Edge-Coloring Bipartite Graphs
• Edge-Coloring Bipartite Graphs
• scientific article; zbMATH DE number 7566051 (Why is no real title available?)
• Subset matching and edge coloring in bipartite graphs
• Asymmetrical multiconnection three‐stage clos networks
• scientific article; zbMATH DE number 6469209 (Why is no real title available?)
• Edge coloring of bipartite graphs with constraints
• Enumeration algorithm for the edge coloring problem on bipartite graphs
• Analysis of approximate algorithms for edge-coloring bipartite graphs
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time

This page was built for publication: Algorithms for edge coloring bipartite graphs

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