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

DOI10.1016/J.TCS.2007.04.006MaRDI QIDQ995582zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Induced Matching in Some Subclasses of Bipartite Graphs
• Maximum weight induced matching in some subclasses of bipartite graphs
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• A min-max property of chordal bipartite graphs with applications
• Finding maximum edge bicliques in convex bipartite graphs

Cites work

• scientific article; zbMATH DE number 434499 (Why is no real title available?)
• scientific article; zbMATH DE number 1445284 (Why is no real title available?)
• Finding a maximum induced matching in weakly chordal graphs
• Graph Classes: A Survey
• Induced matchings
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Irredundancy in circular arc graphs
• New results on induced matchings
• Node-Deletion Problems on Bipartite Graphs
• On maximum induced matchings in bipartite graphs
• On the 2-Chain Subgraph Cover and Related Problems
• On the complexity of the k-chain subgraph cover problem
• Optimizing weakly triangulated graphs
• Threshold Dimension of Graphs

Cited in

(13)

• Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
• Recent progress on strong edge-coloring of graphs
• Well-indumatched pseudoforests
• Induced Matching in Some Subclasses of Bipartite Graphs
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Induced matchings in graphs of degree at most 4
• 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 strongly biconvex graphs and some algebraic applications
• On maximal chain subgraphs and covers of bipartite graphs
• Dominating induced matchings
• Graphs with maximal induced matchings of the same size
• Maximum induced matching problem on hhd-free graphs

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

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