The induced matching and chain subgraph cover problems for convex bipartite graphs

DOI10.1016/j.tcs.2007.04.006zbMath1188.68209OpenAlexW1974918981MaRDI QIDQ995582

Andreas Brandstädt, Elaine M. Eschen, R. Sritharan

Publication date: 3 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.04.006

zbMATH Keywords

induced matchingconvex bipartite graphchain cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

Graphs with maximal induced matchings of the same size ⋮ Induced Matching in Some Subclasses of Bipartite Graphs ⋮ A min-max property of chordal bipartite graphs with applications ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Induced Matchings in Graphs of Degree at Most 4 ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ On Maximal Chain Subgraphs and Covers of Bipartite Graphs ⋮ Maximum induced matching problem on hhd-free graphs ⋮ Dominating Induced Matchings ⋮ Recent progress on strong edge-coloring of graphs ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Irredundancy in circular arc graphs
• Induced matchings
• On the complexity of the k-chain subgraph cover problem
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Finding a maximum induced matching in weakly chordal graphs
• Optimizing weakly triangulated graphs
• On maximum induced matchings in bipartite graphs
• New results on induced matchings
• Threshold Dimension of Graphs
• Node-Deletion Problems on Bipartite Graphs
• Graph Classes: A Survey
• On the 2-Chain Subgraph Cover and Related Problems

This page was built for publication: The induced matching and chain subgraph cover problems for convex bipartite graphs