ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS

DOI10.1142/S1793830912500504zbMath1257.05132MaRDI QIDQ4903635

No author found.

Publication date: 24 January 2013

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

zbMATH Keywords

graph algorithmschain graphsNP-completeperfect elimination bipartite graphsacyclic matchingbipartite permutation graphs

Mathematics Subject Classification ID

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

Related Items (7)

Acyclic Matching in Some Subclasses of Graphs ⋮ Acyclic matchings in graphs of bounded maximum degree ⋮ On the parameterized complexity of the acyclic matching problem ⋮ Acyclic matching in some subclasses of graphs ⋮ Degenerate matchings and edge colorings ⋮ Approximating maximum acyclic matchings by greedy and local search strategies ⋮ On some hard and some tractable cases of the maximum acyclic matching problem

Cites Work

• Unnamed Item
• Bandwidth of chain graphs
• Bipartite permutation graphs with application to the minimum buffer size problem
• Bipartite permutation graphs
• Generalized subgraph-restricted matchings in graphs
• Node-Deletion NP-Complete Problems
• Node-Deletion Problems on Bipartite Graphs
• Perfect Elimination and Chordal Bipartite Graphs

This page was built for publication: ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS