Some Matching Problems for Bipartite Graphs

DOI10.1145/322092.322093zbMath0388.68059OpenAlexW2000304327MaRDI QIDQ4170253

Alon Itai, Steven L. Tanimoto, Michael Rodeh

Publication date: 1978

Published in: Journal of the ACM (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Graph theory (including graph drawing) in computer science (68R10)

Related Items (38)

Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games ⋮ Traveling salesman problems in temporal graphs ⋮ Complexity results for rainbow matchings ⋮ Coloured matchings in bipartite graphs ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective ⋮ Graph matching problems and the NP-hardness of sortedness constraints ⋮ The complexity of matching with bonds ⋮ A weighted perfect matching with constraints on weights of its parts ⋮ Degree switching operations in networks and large scale systems assignment problems ⋮ Integrality gaps for colorful matchings ⋮ Minimum <scp>color‐degree</scp> perfect b‐matchings ⋮ The Complexity of Bottleneck Labeled Graph Problems ⋮ Embedding of complete graphs in broken Chimera graphs ⋮ Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings ⋮ An NP-complete matching problem ⋮ A theory of rectangular dual graphs ⋮ Bi-criteria and approximation algorithms for restricted matchings ⋮ Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids ⋮ Parameterized algorithms and kernels for rainbow matching ⋮ Self-organized Anonymous Authentication in Mobile Ad Hoc Networks ⋮ Budgeted colored matching problems ⋮ Decomposition of university course timetabling. A systematic study of subproblems and their complexities ⋮ Matchings under distance constraints. I ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ On complexity of special maximum matchings constructing ⋮ Maximum weight edge-constrained matchings ⋮ On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems ⋮ Path colorings in bipartite graphs ⋮ Minimum-diameter covering problems ⋮ Assignment problem with conflicts ⋮ A note on the hardness results for the labeled perfect matching problems in bipartite graphs ⋮ Neighborhood portfolio approach for local search applied to timetabling problems ⋮ Algorithms and complexity for a class of combinatorial optimization problems with labelling ⋮ Selecting and covering colored points ⋮ The labeled perfect matching in bipartite graphs ⋮ Parameterized Algorithms and Kernels for Rainbow Matching ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective^* ⋮ From one to many rainbow Hamiltonian cycles

This page was built for publication: Some Matching Problems for Bipartite Graphs