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
From MaRDI portal
Publication:1762983
DOI10.1007/s00453-003-1035-4zbMath1082.68592OpenAlexW2032987509MaRDI QIDQ1762983
Publication date: 11 February 2005
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-003-1035-4
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (60)
Disconnected matchings ⋮ On the computational complexity of the Helly number in the \(P_3\) and related convexities ⋮ Acyclic matchings in graphs of bounded maximum degree ⋮ Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ On graphs with induced matching number almost equal to matching number ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graphs with maximal induced matchings of the same size ⋮ Exact algorithms for maximum induced matching ⋮ On the hardness of deciding the equality of the induced and the uniquely restricted matching number ⋮ Maximum matching in multi-interface networks ⋮ On the parameterized complexity of the acyclic matching problem ⋮ Vertex-decomposable graphs, codismantlability, Cohen-Macaulayness, and Castelnuovo-Mumford regularity ⋮ Computational complexity aspects of super domination ⋮ Maximum Induced Matchings in Grids ⋮ Unnamed Item ⋮ Tree-Width and Optimization in Bounded Degree Graphs ⋮ Weighted connected matchings ⋮ Boundary Classes of Planar Graphs ⋮ Locally searching for large induced matchings ⋮ Induced Matching in Some Subclasses of Bipartite Graphs ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ Parameterized algorithms and kernels for almost induced matching ⋮ Well-indumatched Trees and Graphs of Bounded Girth ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ Prime graphs, matchings and the Castelnuovo-Mumford regularity ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Generalizing the induced matching by edge capacity constraints ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ Approximating weighted induced matchings ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ Induced Matchings in Graphs of Degree at Most 4 ⋮ On the approximability of the maximum induced matching problem ⋮ Approximating maximum acyclic matchings by greedy and local search strategies ⋮ 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 ⋮ On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs ⋮ New kernels for several problems on planar graphs ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ Equality of distance packing numbers ⋮ Sparse regular induced subgraphs in \(2P_3\)-free graphs ⋮ Efficient edge domination in regular graphs ⋮ Maximum induced matchings for chordal graphs in linear time ⋮ The parameterized complexity of the induced matching problem ⋮ Disconnected matchings ⋮ Dominating Induced Matchings ⋮ On Distance-3 Matchings and Induced Matchings ⋮ Recent progress on strong edge-coloring of graphs ⋮ Brambles and independent packings in chordal graphs ⋮ The graphs with maximum induced matching and maximum matching the same size ⋮ Independent packings in structured graphs ⋮ Squares of Intersection Graphs and Induced Matchings ⋮ Maximum induced matchings close to maximum matchings ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ 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
This page was built for publication: 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
