Acyclic matching in some subclasses of graphs

DOI10.1016/j.tcs.2022.12.008OpenAlexW4311085763MaRDI QIDQ2680984

B. S. Panda, Juhi Chaudhary

Publication date: 5 January 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.12.008

zbMATH Keywords

matchinggraph algorithmspolynomial-time algorithmsacyclic matching\( \mathsf{NP} \)-completeness\( \mathsf{APX} \)-completeness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

On the parameterized complexity of the acyclic matching problem

Cites Work

• A linear time recognition algorithm for proper interval graphs
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Domination in some subclasses of bipartite graphs
• Degenerate matchings and edge colorings
• Generalized subgraph-restricted matchings in graphs
• Approximating maximum acyclic matchings by greedy and local search strategies
• On some hard and some tractable cases of the maximum acyclic matching problem
• Optimal greedy algorithms for indifference graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• A REVIEW OF TREE CONVEX SETS TEST
• ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS
• Acyclic Matching in Some Subclasses of Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Acyclic matching in some subclasses of graphs