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

Graph algorithms (graph-theoretic aspects) (05C85) 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)

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

(18)

• Edge-Coloring Bipartite Graphs
• Distributed edge coloration for bipartite networks
• Asymmetrical multiconnection three‐stage clos networks
• Edge coloring of bipartite graphs with constraints
• Space-efficient Euler partition and bipartite edge coloring
• On the enumeration of bipartite minimum edge colorings
• scientific article; zbMATH DE number 7566051 (Why is no real title available?)
• scientific article; zbMATH DE number 6469209 (Why is no real title available?)
• Combinatorial analysis (nonnegative matrices, algorithmic problems)
• Another look at the degree constrained subgraph problem
• Solving matching problems efficiently in bipartite graphs
• Finding 1-Factors in Bipartite Regular Graphs and Edge-Coloring Bipartite Graphs
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• The edge-cochromatic number of bipartite graph
• 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
• Enumeration algorithm for the edge coloring problem on bipartite graphs
• Subset matching and edge coloring in bipartite graphs

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)