Finding a maximum induced matching in weakly chordal graphs

DOI10.1016/S0012-365X(02)00803-8zbMath1022.05064OpenAlexW1977889556MaRDI QIDQ1810638

R. Sritharan, Kathie Cameron, 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

zbMATH Keywords

polynomial-time algorithm intersection graphs induced matching strong chromatic index strong matching strong edge-colouring weakly chordal graphs interval-filament graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graphs with maximal induced matchings of the same size ⋮ On the parameterized complexity of the acyclic matching problem ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Induced matchings in strongly biconvex graphs and some algebraic applications ⋮ Maximum Induced Matchings in Grids ⋮ Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences ⋮ Induced Matching in Some Subclasses of Bipartite Graphs ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ A min-max property of chordal bipartite graphs with applications ⋮ Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ Approximating weighted induced matchings ⋮ Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ Induced Matchings in Graphs of Degree at Most 4 ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ On the approximability of the maximum induced matching problem ⋮ On distance-3 matchings and induced matchings ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ Maximum weight induced matching in some subclasses of bipartite graphs ⋮ The complexity of dissociation set problems in graphs ⋮ The induced separation dimension of a graph ⋮ The induced matching and chain subgraph cover problems for convex bipartite graphs ⋮ New kernels for several problems on planar graphs ⋮ Some bounds on the maximum induced matching numbers of certain grids ⋮ Equality of distance packing numbers ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ Maximum induced matchings for chordal graphs in linear time ⋮ On the induced matching problem in Hamiltonian bipartite graphs ⋮ The parameterized complexity of the induced matching problem ⋮ Maximum induced matching problem on hhd-free graphs ⋮ On Distance-3 Matchings and Induced Matchings ⋮ Recent progress on strong edge-coloring of graphs ⋮ The \(\text{v} \)-number of monomial ideals ⋮ Brambles and independent packings in chordal graphs ⋮ The graphs with maximum induced matching and maximum matching the same size ⋮ Independent packings in structured graphs ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs ⋮ Moderately exponential time algorithms for the maximum induced matching problem ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Cites Work