Acyclic matching in some subclasses of graphs

DOI10.1016/J.TCS.2022.12.008MaRDI QIDQ2680984zbMATH OpenOpenAlexFDO

Authors 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

\( \mathsf{APX} \)-completeness\( \mathsf{NP} \)-completenessacyclic matchinggraph algorithmsmatchingpolynomial-time algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Acyclic matchings in subclasses of bipartite graphs
• On some hard and some tractable cases of the maximum acyclic matching problem
• Acyclic matchings in graphs of bounded maximum degree
• Induced Matching in Some Subclasses of Bipartite Graphs
• A lower bound on the acyclic matching number of subcubic graphs

Cites work

• A linear time recognition algorithm for proper interval graphs
• A review of tree convex sets test
• Acyclic Matching in Some Subclasses of Graphs
• Acyclic matchings in subclasses of bipartite graphs
• Approximating maximum acyclic matchings by greedy and local search strategies
• Degenerate matchings and edge colorings
• Domination in some subclasses of bipartite graphs
• Generalized subgraph-restricted matchings in graphs
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• On some hard and some tractable cases of the maximum acyclic matching problem
• Optimal greedy algorithms for indifference graphs
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs

Cited in

(15)

• A lower bound on the acyclic matching number of subcubic graphs
• Acyclic matchings in graphs of bounded maximum degree
• On some hard and some tractable cases of the maximum acyclic matching problem
• Acyclic matchings
• Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs
• Acyclic matchings in subclasses of bipartite graphs
• Acyclic Matching in Some Subclasses of Graphs
• On the parameterized complexity of the acyclic matching problem
• Parameterized Results on Acyclic Matchings with Implications for Related Problems
• On the complexity of minimum maximal acyclic matchings
• Minimum maximal acyclic matching in proper interval graphs
• Parameterized results on acyclic matchings with implications for related problems
• \(\mathcal{P}\)-matchings parameterized by treewidth
• Weighted connected matchings
• Structural parameterizations for induced and acyclic matching

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2680984)