Acyclic Matching in Some Subclasses of Graphs

DOI10.1007/978-3-030-48966-3_31OpenAlexW3030295680MaRDI QIDQ5041209FDOQ5041209

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

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

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)

Cites Work

• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• A review of tree convex sets test
• Generalized subgraph-restricted matchings in graphs
• A linear time recognition algorithm for proper interval graphs
• Title not available (Why is that?)
• A lower bound on the acyclic matching number of subcubic graphs
• Degenerate matchings and edge colorings
• Acyclic matchings in subclasses of bipartite graphs
• On some hard and some tractable cases of the maximum acyclic matching problem

Cited In (14)

• 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
• Minimum maximal acyclic matching in proper interval graphs

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)