Acyclic Matching in Some Subclasses of Graphs

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

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

matchinggraph algorithmapproximation algorithmNP-completenessbipartite graphschordal graphs

Mathematics Subject Classification ID

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

Related Items (7)

Disconnected matchings ⋮ Acyclic matching in some subclasses of graphs ⋮ Minimum maximal acyclic matching in proper interval graphs ⋮ Weighted connected matchings ⋮ On the complexity of minimum maximal acyclic matchings ⋮ On the complexity of minimum maximal uniquely restricted matching ⋮ Disconnected matchings

Cites Work

• Unnamed Item
• Unnamed Item
• A linear time recognition algorithm for proper interval graphs
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• A lower bound on the acyclic matching number of subcubic graphs
• Degenerate matchings and edge colorings
• Generalized subgraph-restricted matchings in graphs
• On some hard and some tractable cases of the maximum acyclic matching problem
• 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

This page was built for publication: Acyclic Matching in Some Subclasses of Graphs