Some Matching Problems for Bipartite Graphs
From MaRDI portal
Publication:4170253
DOI10.1145/322092.322093zbMATH Open0388.68059OpenAlexW2000304327MaRDI QIDQ4170253FDOQ4170253
Authors: Alon Itai, Michael Rodeh, Steven L. Tanimoto 
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Determinants, permanents, traces, other special matrix functions (15A15)
Cited In (39)
- An NP-complete matching problem
- From one to many rainbow Hamiltonian cycles
- A note on the hardness results for the labeled perfect matching problems in bipartite graphs
- Parameterized algorithms and kernels for rainbow matching
- Parameterized Algorithms and Kernels for Rainbow Matching
- Traveling salesman problems in temporal graphs
- Budgeted colored matching problems
- Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
- A theory of rectangular dual graphs
- Graph matching problems and the NP-hardness of sortedness constraints
- The complexity of matching with bonds
- Matchings under distance constraints. I
- Matchings under distance constraints. II.
- The labeled perfect matching in bipartite graphs
- Bi-criteria and approximation algorithms for restricted matchings
- Complexity results for rainbow matchings
- On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems
- Coloured matchings in bipartite graphs
- Maximum weight edge-constrained matchings
- Minimum-diameter covering problems
- An introduction to temporal graphs: an algorithmic perspective
- An introduction to temporal graphs: an algorithmic perspective
- Minimum <scp>color‐degree</scp> perfect b‐matchings
- The Complexity of Bottleneck Labeled Graph Problems
- Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games
- A weighted perfect matching with constraints on weights of its parts
- Selecting and covering colored points
- Assignment problem with conflicts
- Neighborhood portfolio approach for local search applied to timetabling problems
- Self-organized anonymous authentication in mobile ad hoc networks
- Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
- Degree switching operations in networks and large scale systems assignment problems
- Path colorings in bipartite graphs
- Embedding of complete graphs in broken Chimera graphs
- Decomposition of university course timetabling. A systematic study of subproblems and their complexities
- Integrality gaps for colorful matchings
- On complexity of special maximum matchings constructing
- Algorithms and complexity for a class of combinatorial optimization problems with labelling
- Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
This page was built for publication: Some Matching Problems for Bipartite Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4170253)
