New results on induced matchings

DOI10.1016/S0166-218X(99)00194-8zbMath0951.68104OpenAlexW1974366154MaRDI QIDQ1975379

Martin Charles Golumbic, Moshe Lewenstein

Publication date: 11 December 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00194-8

zbMATH Keywords

matchinggraph theoryindependent setperfect graphinduced matchingstrong matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Perfect graphs (05C17)

Related Items (69)

A polynomial time algorithm for strong edge coloring of partial \(k\)-trees ⋮ Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem ⋮ Unnamed Item ⋮ Graphs with maximal induced matchings of the same size ⋮ A characterization of well-indumatchable graphs having girth greater than seven ⋮ Exact algorithms for maximum induced matching ⋮ Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs ⋮ Maximum matching in multi-interface networks ⋮ On the parameterized complexity of the acyclic matching problem ⋮ Computational complexity aspects of super domination ⋮ Matchings, coverings, and Castelnuovo-Mumford regularity ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Induced matchings in strongly biconvex graphs and some algebraic applications ⋮ Strong edge-coloring for cubic Halin graphs ⋮ Strong edge chromatic index of the generalized Petersen graphs ⋮ The strong chromatic index of Halin graphs ⋮ Maximum Induced Matchings in Grids ⋮ Unnamed Item ⋮ Upper bounds for the strong chromatic index of Halin graphs ⋮ Tree-Width and Optimization in Bounded Degree Graphs ⋮ On the strong chromatic index of cubic Halin graphs ⋮ Induced Matching in Some Subclasses of Bipartite Graphs ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ Induced matchings in asteroidal triple-free graphs ⋮ Parameterized algorithms and kernels for almost induced matching ⋮ A min-max property of chordal bipartite graphs with applications ⋮ Induced matchings in intersection graphs. ⋮ Well-indumatched Trees and Graphs of Bounded Girth ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ 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 ⋮ On distance-3 matchings and induced matchings ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ Generalized subgraph-restricted matchings in graphs ⋮ Maximum weight induced matching in some subclasses of bipartite graphs ⋮ Number of induced matchings of graphs ⋮ The induced separation dimension of a graph ⋮ Maximum induced matching of hexagonal graphs ⋮ The induced matching and chain subgraph cover problems for convex bipartite graphs ⋮ New kernels for several problems on planar graphs ⋮ Strong edge-coloring for jellyfish graphs ⋮ Equality of distance packing numbers ⋮ Efficient edge domination in regular graphs ⋮ Proof of a conjecture on the strong chromatic index of Halin graphs ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ Finding a maximum induced matching in weakly chordal graphs ⋮ Maximum induced matchings for chordal graphs in linear time ⋮ The parameterized complexity of the induced matching problem ⋮ Some results on graphs without long induced paths ⋮ Induced packing of odd cycles in planar graphs ⋮ Maximum induced matching problem on hhd-free graphs ⋮ 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 ⋮ On maximum induced matchings in bipartite graphs ⋮ Independent packings in structured graphs ⋮ Squares of Intersection Graphs and Induced Matchings ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ On the computational complexity of strong edge coloring ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs ⋮ Maximum induced matchings of random cubic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trapezoid graphs and generalizations, geometry and algorithms
• Irredundancy in circular arc graphs
• Trapezoid graphs and their coloring
• Linear time algorithms on circular-arc graphs
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• Comparability graphs and a new matroid
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Induced matchings
• Minimum Cuts for Circular-Arc Graphs
• Stability in circular arc graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: New results on induced matchings