Complexity of a disjoint matching problem on bipartite graphs

DOI10.1016/j.ipl.2016.05.005zbMath1364.05056arXiv1506.06157OpenAlexW2963591777MaRDI QIDQ2629777

Gregory J. Puleo

Publication date: 7 July 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.06157

zbMATH Keywords

computational complexityedge coloringbipartite graphsmatchingsNP-hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings, Supermodularity in Unweighted Graph Optimization II: Matroidal Term Rank Augmentation

Cites Work

• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• On complexity of special maximum matchings constructing
• Disjoint matchings of graphs
• Complexity of a 3-dimensional assignment problem
• On Representatives of Subsets
• Subgraphs with prescribed valencies
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• The Maximum Number of Disjoint Permutations Contained in a Matrix of Zeros and Ones