Acyclic matchings in subclasses of bipartite graphs

DOI10.1142/S1793830912500504MaRDI QIDQ4903635zbMATH OpenFDO

Authors

Publication date 24 January 2013

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

zbMATH Keywords

graph algorithmsNP-completechain graphsperfect elimination bipartite graphsacyclic matchingbipartite permutation graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Acyclic matching in some subclasses of graphs
• On some hard and some tractable cases of the maximum acyclic matching problem
• Acyclic matchings in graphs of bounded maximum degree
• A lower bound on the acyclic matching number of subcubic graphs
• Alternating cycle-free matchings

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Bandwidth of chain graphs
• Bipartite permutation graphs
• Bipartite permutation graphs with application to the minimum buffer size problem
• Generalized subgraph-restricted matchings in graphs
• Node-Deletion NP-Complete Problems
• Node-Deletion Problems on Bipartite Graphs
• Perfect Elimination and Chordal Bipartite Graphs

Cited in

(12)

• Acyclic Matching in Some Subclasses of Graphs
• Approximating maximum acyclic matchings by greedy and local search strategies
• A lower bound on the acyclic matching number of subcubic graphs
• Degenerate matchings and edge colorings
• On some hard and some tractable cases of the maximum acyclic matching problem
• Acyclic matchings in graphs of bounded maximum degree
• On the parameterized complexity of the acyclic matching problem
• On the complexity of minimum maximal acyclic matchings
• Acyclic 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

This page was built for publication: Acyclic matchings in subclasses of bipartite graphs

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