On the complexity of minimum maximal uniquely restricted matching
From MaRDI portal
Publication:5918362
DOI10.1016/j.tcs.2021.05.036OpenAlexW3110710068MaRDI QIDQ5918362
Publication date: 11 August 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.05.036
matchinggraph algorithmsuniquely restricted matchingpolynomial time algorithms\( \mathsf{NP} \)-completeness\( \mathsf{APX} \)-completeness
Related Items (2)
Minimum maximal acyclic matching in proper interval graphs ⋮ On the complexity of minimum maximal acyclic matchings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bipartite permutation graphs with application to the minimum buffer size problem
- A linear time recognition algorithm for proper interval graphs
- Independent domination in chordal graphs
- Optimization, approximation, and complexity classes
- Alternating cycle-free matchings
- Domination in some subclasses of bipartite graphs
- On the complexity of minimum cardinality maximal uniquely restricted matching in graphs
- Uniquely restricted matchings and edge colorings
- Generalized subgraph-restricted matchings in graphs
- Independent domination in graphs: A survey and recent results
- On the Maximum Uniquely Restricted Matching for Bipartite Graphs
- Uniquely Restricted Matchings in Interval Graphs
- A REVIEW OF TREE CONVEX SETS TEST
- Acyclic Matching in Some Subclasses of Graphs
- On the complexity of minimum maximal uniquely restricted matching
- Uniquely restricted matchings
This page was built for publication: On the complexity of minimum maximal uniquely restricted matching
