Acyclic Matching in Some Subclasses of Graphs

DOI10.1007/978-3-030-48966-3_31MaRDI QIDQ5041209zbMATH OpenOpenAlexFDO

Authors B. S. Panda, Juhi Chaudhary

Publication date 13 October 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-48966-3_31

zbMATH Keywords

matchingapproximation algorithmgraph algorithmNP-completenesschordal graphsbipartite graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Recommendations

• Acyclic matching in some subclasses of graphs
• Acyclic matchings in subclasses of bipartite graphs
• Minimum maximal acyclic matching in proper interval graphs
• On the complexity of minimum maximal acyclic matchings
• On the parameterized complexity of the acyclic matching problem

Cites work

• scientific article; zbMATH DE number 4152428 (Why is no real title available?)
• A linear time recognition algorithm for proper interval graphs
• A lower bound on the acyclic matching number of subcubic graphs
• A review of tree convex sets test
• Acyclic matchings in subclasses of bipartite graphs
• Degenerate matchings and edge colorings
• Generalized subgraph-restricted matchings in graphs
• 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
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs

Cited in

(14)

• Minimum maximal acyclic matching in proper interval graphs
• A lower bound on the acyclic matching number of subcubic graphs
• On the parameterized complexity of the acyclic matching problem
• Weighted connected matchings
• On the complexity of minimum maximal acyclic matchings
• Acyclic matchings
• Parameterized Results on Acyclic Matchings with Implications for Related Problems
• Disconnected matchings
• Disconnected matchings
• Acyclic matching in some subclasses of graphs
• Minimum maximal acyclic matching in proper interval graphs
• Parameterized results on acyclic matchings with implications for related problems
• On the complexity of minimum maximal uniquely restricted matching
• On the complexity of minimum maximal acyclic matchings

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 Q5041209)