Solving matching problems efficiently in bipartite graphs

DOI10.1007/978-3-319-19315-1_12MaRDI QIDQ2946048zbMATH OpenOpenAlexFDO

Authors Selma Djelloul

Publication date 15 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-19315-1_12

Mathematics Subject Classification ID

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

Recommendations

• Algorithms for edge coloring bipartite graphs
• scientific article; zbMATH DE number 1104328
• Bipartite Edge Coloring in O(\Delta m) Time
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Bicolored matchings in some classes of graphs

Cites work

• A constructive characterization of trees with at least k disjoint maximum matchings
• A simple existence criterion for \((g<f)\)-factors
• Colorings with few colors: counting, enumeration and combinatorial bounds
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Counting the number of matchings in chordal and chordal bipartite graph classes
• Covering the edges with consecutive sets
• Difference graphs
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• scientific article; zbMATH DE number 1256776 (Why is no real title available?)
• scientific article; zbMATH DE number 1342090 (Why is no real title available?)
• scientific article; zbMATH DE number 4193736 (Why is no real title available?)
• scientific article; zbMATH DE number 3325507 (Why is no real title available?)
• Improved edge-coloring with three colors
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Node-Deletion Problems on Bipartite Graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Some results on an edge coloring problem of Folkman and Fulkerson
• The disjoint paths problem in quadratic time
• The NP-Completeness of Edge-Coloring
• Tutte's edge-colouring conjecture

Cited in

(13)

• The uniquely solvable bipartite matching problem
• Optimum matchings in weighted bipartite graphs
• On the computational complexity of the bipartizing matching problem
• scientific article; zbMATH DE number 5909229 (Why is no real title available?)
• scientific article; zbMATH DE number 4074794 (Why is no real title available?)
• scientific article; zbMATH DE number 1054930 (Why is no real title available?)
• Making bipartite graphs DM-irreducible
• An extendable stable matching algorithm of a kind of bipartite graph
• scientific article; zbMATH DE number 4197736 (Why is no real title available?)
• A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs
• Semi-matchings for bipartite graphs and load balancing
• Finding strongly popular \(b\)-matchings in bipartite graphs
• Solving (large scale) matching problems combinatorially

This page was built for publication: Solving matching problems efficiently in bipartite graphs

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