Solving Matching Problems Efficiently in Bipartite Graphs

DOI10.1007/978-3-319-19315-1_12zbMath1401.05231OpenAlexW1170606744MaRDI QIDQ2946048

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• A simple existence criterion for \((g<f)\)-factors
• Improved edge-coloring with three colors
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• A constructive characterization of trees with at least k disjoint maximum matchings
• Tutte's edge-colouring conjecture
• Some results on an edge coloring problem of Folkman and Fulkerson
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Colorings with few colors: counting, enumeration and combinatorial bounds
• Node-Deletion Problems on Bipartite Graphs
• The NP-Completeness of Edge-Coloring
• Covering the edges with consecutive sets
• Perfect Elimination and Chordal Bipartite Graphs
• Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes
• Difference graphs

This page was built for publication: Solving Matching Problems Efficiently in Bipartite Graphs