On the complexity of minimum maximal acyclic matchings
From MaRDI portal
Publication:6168934
DOI10.1007/978-3-031-22105-7_10MaRDI QIDQ6168934
Juhi Chaudhary, Sounaka Mishra, B. S. Panda
Publication date: 10 August 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
matchingacyclic matching\textsf{NP}-completenessminimum maximal acyclic matching\textsf{APX}-hardness
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
- On the max min vertex cover problem
- A simplified NP-complete satisfiability problem
- Approximability results for the maximum and minimum maximal induced matching problems
- Optimization, approximation, and complexity classes
- On the complexity of minimum cardinality maximal uniquely restricted matching in graphs
- The many facets of upper domination
- Generalized subgraph-restricted matchings in graphs
- Independent domination in graphs: A survey and recent results
- (In)approximability of maximum minimal FVS
- Uniquely restricted matchings in subcubic graphs
- A Linear Algorithm for Computing of a Minimum Weight Maximal Induced Matching in an Edge-Weighted Tree
- Node-Deletion NP-Complete Problems
- Edge Dominating Sets in Graphs
- Perfect Elimination and Chordal Bipartite Graphs
- Acyclic Matching in Some Subclasses of Graphs
- On the approximability of the maximum common subgraph problem
- Paths, Trees, and Flowers
- On the complexity of minimum maximal uniquely restricted matching
