Finding maximum induced matchings in subclasses of claw-free and P₅-free graphs, and in graphs with matching and induced matching of equal maximum size

DOI10.1007/S00453-003-1035-4zbMATH Open1082.68592OpenAlexW2032987509MaRDI QIDQ1762983FDOQ1762983

Authors: Daniel Kobler, Udi Rotics 

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

Recommendations

• New results on induced matchings
• Maximum induced matching of hexagonal graphs
• Induced matchings
• Finding a maximum induced matching in weakly chordal graphs
• Maximum induced matchings for chordal graphs in linear time

zbMATH Keywords

Polynomial algorithmsClaw-free graphsInduced matchingRegular graphsBullLine-graphs

Mathematics Subject Classification ID

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)

Cited In (67)

• Maximum matching in multi-interface networks
• The graphs with maximum induced matching and maximum matching the same size
• Induced Matching in Some Subclasses of Bipartite Graphs
• Independent packings in structured graphs
• Maximum regular induced subgraphs in \(2P_3\)-free graphs
• Approximating weighted induced matchings
• Boundary Classes of Planar Graphs
• Almost induced matching: linear kernels and parameterized algorithms
• The complexity of dissociation set problems in graphs
• On the computational complexity of the Helly number in the \(P_3\) and related convexities
• Approximating maximum acyclic matchings by greedy and local search strategies
• Parameterized algorithms and kernels for almost induced matching
• Induced matchings in graphs of degree at most 4
• Maximum induced matching of hexagonal graphs
• Vertex-decomposable graphs, codismantlability, Cohen-Macaulayness, and Castelnuovo-Mumford regularity
• On some hard and some tractable cases of the maximum acyclic matching problem
• Exact algorithms for maximum induced matching
• Sparse regular induced subgraphs in \(2P_3\)-free graphs
• Acyclic matchings in graphs of bounded maximum degree
• On the parameterized complexity of the acyclic matching problem
• A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
• Maximum weight induced matching in some subclasses of bipartite graphs
• Weighted connected matchings
• On the hardness of deciding the equality of the induced and the uniquely restricted matching number
• Generalizing the induced matching by edge capacity constraints
• Maximum Induced Matchings in Grids
• On graphs with induced matching number almost equal to matching number
• Graphs with maximal induced matchings of the same size
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Disconnected matchings
• Disconnected matchings
• NP-hard graph problems and boundary classes of graphs
• Brambles and independent packings in chordal graphs
• Efficient edge domination in regular graphs
• The parameterized complexity of the induced matching problem
• Moderately exponential time algorithms for the maximum induced matching problem
• Parameterized complexity of induced graph matching on claw-free graphs
• New kernels for several problems on planar graphs
• Squares of Intersection Graphs and Induced Matchings
• Maximum induced matching algorithms via vertex ordering characterizations
• Maximum induced matching algorithms via vertex ordering characterizations
• On distance-3 matchings and induced matchings
• Dominating induced matchings
• Equality of distance packing numbers
• Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
• Approximability results for the maximum and minimum maximal induced matching problems
• Maximum induced matchings for chordal graphs in linear time
• Recent progress on strong edge-coloring of graphs
• Tree-Width and Optimization in Bounded Degree Graphs
• Locally searching for large induced matchings
• On the approximability of the maximum induced matching problem
• Perfectly matched sets in graphs: parameterized and exact computation
• Prime graphs, matchings and the Castelnuovo-Mumford regularity
• Well-indumatched Trees and Graphs of Bounded Girth
• On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs
• Finding a maximum induced matching in weakly chordal graphs
• Maximum induced matchings close to maximum matchings
• 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
• A bisection approach to subcubic maximum induced matching
• Computational complexity aspects of super domination
• Maximal induced matchings in \(K_4\)-free and \(K_5\)-free graphs
• On distance-3 matchings and induced matchings
• An improved kernel and parameterized algorithm for almost induced matching
• Edge open packing: complexity, algorithmic aspects, and bounds
• Well-indumatched pseudoforests

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

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