On the complexity of minimum maximal acyclic matchings
From MaRDI portal
Publication:6168934
DOI10.1007/978-3-031-22105-7_10MaRDI QIDQ6168934FDOQ6168934
Authors: 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
Cites Work
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Paths, Trees, and Flowers
- Matching theory
- A Linear Algorithm for Computing of a Minimum Weight Maximal Induced Matching in an Edge-Weighted Tree
- Node-Deletion NP-Complete Problems
- A simplified NP-complete satisfiability problem
- Title not available (Why is that?)
- Independent domination in graphs: A survey and recent results
- Edge Dominating Sets in Graphs
- Perfect Elimination and Chordal Bipartite Graphs
- On the approximability of the maximum common subgraph problem
- Approximability results for the maximum and minimum maximal induced matching problems
- Generalized subgraph-restricted matchings in graphs
- Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
- On the max min vertex cover problem
- The many facets of upper domination
- Acyclic Matching in Some Subclasses of Graphs
- On the complexity of minimum cardinality maximal uniquely restricted matching in graphs
- Uniquely restricted matchings in subcubic graphs
- (In)approximability of maximum minimal FVS
- On the complexity of minimum maximal uniquely restricted matching
Cited In (4)
This page was built for publication: On the complexity of minimum maximal acyclic matchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168934)
