Finding a maximum induced matching in weakly chordal graphs
From MaRDI portal
Publication:1810638
DOI10.1016/S0012-365X(02)00803-8zbMATH Open1022.05064OpenAlexW1977889556MaRDI QIDQ1810638FDOQ1810638
Authors: Kathie Cameron, R. Sritharan, Yingwen Tang 
Publication date: 9 June 2003
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0012-365x(02)00803-8
Recommendations
- On maximum induced matchings in bipartite graphs
- Induced matchings
- Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
- New results on induced matchings
- Induced Matching in Some Subclasses of Bipartite Graphs
intersection graphsinduced matchingpolynomial-time algorithmstrong chromatic indexstrong matchingstrong edge-colouringweakly chordal graphsinterval-filament graphs
Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Graph Classes: A Survey
- Comparability graphs and intersection graphs
- Induced matchings
- Weakly triangulated graphs
- Thresholds for classes of intersection graphs
- Induced matchings in asteroidal triple-free graphs
- Maximum weight independent sets and cliques in intersection graphs of filaments
- NP-completeness of some generalizations of the maximum matching problem
- Algorithms for weakly triangulated graphs
- New results on induced matchings
- Covering and coloring polygon-circle graphs
- Induced matchings in intersection graphs
- Optimizing weakly triangulated graphs
- Title not available (Why is that?)
- Irredundancy in circular arc graphs
- Title not available (Why is that?)
Cited In (49)
- Approximation of knapsack problems with conflict and forcing graphs
- Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
- The graphs with maximum induced matching and maximum matching the same size
- Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs with special blocks
- Induced Matching in Some Subclasses of Bipartite Graphs
- Some bounds on the maximum induced matching numbers of certain grids
- Independent packings in structured graphs
- Approximating weighted induced matchings
- The complexity of dissociation set problems in graphs
- Induced matchings in graphs of degree at most 4
- The induced separation dimension of a graph
- Maximum induced matching problem on hhd-free graphs
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- New min-max theorems for weakly chordal and dually chordal graphs
- On the parameterized complexity of the acyclic matching problem
- Maximum weight induced matching in some subclasses of bipartite graphs
- A min-max property of chordal bipartite graphs with applications
- Maximum Induced Matchings in Grids
- Graphs with maximal induced matchings of the same size
- On the complexity of the dominating induced matching problem in hereditary classes of graphs
- Induced matchings in strongly biconvex graphs and some algebraic applications
- Brambles and independent packings in chordal graphs
- The parameterized complexity of the induced matching problem
- Moderately exponential time algorithms for the maximum induced matching problem
- On distance-3 matchings and induced matchings
- Edge open packing: complexity, algorithmic aspects, and bounds
- New kernels for several problems on planar graphs
- Maximum induced matching algorithms via vertex ordering characterizations
- Maximum induced matching algorithms via vertex ordering characterizations
- On distance-3 matchings and induced matchings
- On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs
- Equality of distance packing numbers
- Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
- Well-indumatched pseudoforests
- Approximability results for the maximum and minimum maximal induced matching problems
- Maximum induced matchings for chordal graphs in linear time
- The induced matching and chain subgraph cover problems for convex bipartite graphs
- Large Induced Subgraphs via Triangulations and CMSO
- Recent progress on strong edge-coloring of graphs
- Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
- The \(\text{v} \)-number of monomial ideals
- A constant factor approximation algorithm for boxicity of circular arc graphs
- On the approximability of the maximum induced matching problem
- Perfectly matched sets in graphs: parameterized and exact computation
- On the induced matching problem in Hamiltonian bipartite graphs
- Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
- Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
This page was built for publication: Finding a maximum induced matching in weakly chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1810638)
