On distance-3 matchings and induced matchings
From MaRDI portal
Publication:716178
DOI10.1016/j.dam.2010.05.022zbMath1210.05105OpenAlexW2124966524MaRDI QIDQ716178
Raffaele Mosca, Andreas Brandstädt
Publication date: 19 April 2011
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.05.022
chordal graphsstrongly chordal graphsdistance-\(k\) matchingmaximum distance-\(k\) matching problemmaximum induced matching problem
Related Items (16)
Graphs with maximal induced matchings of the same size ⋮ Maximum matching in multi-interface networks ⋮ Induced matchings in subcubic graphs without short cycles ⋮ Clique‐width: Harnessing the power of atoms ⋮ Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences ⋮ Exploiting hidden structure in selecting dimensions that distinguish vectors ⋮ Locally searching for large induced matchings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Two greedy consequences for maximum induced matchings ⋮ Approximating weighted induced matchings ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ Equality of distance packing numbers ⋮ Maximum induced matching problem on hhd-free graphs ⋮ Approximating maximum uniquely restricted matchings in bipartite graphs
Cites Work
- Irredundancy in circular arc graphs
- On induced matchings
- On independent vertex sets in subclasses of apple-free graphs
- Induced matchings in bipartite graphs
- Approximability results for the maximum and minimum maximal induced matching problems
- Maximum induced matchings for chordal graphs in linear time
- The parameterized complexity of the induced matching problem
- Characterizations of strongly chordal graphs
- Decomposition by clique separators
- Problems and results in combinatorial analysis and graph theory
- NP-completeness of some generalizations of the maximum matching problem
- Induced matchings
- Modular decomposition and transitive orientation
- On linear and circular structure of (claw, net)-free graphs
- Induced matchings in asteroidal triple-free graphs
- Induced matchings in intersection 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
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- On the approximability of the maximum induced matching problem
- Finding a maximum induced matching in weakly chordal graphs
- On maximum induced matchings in bipartite graphs
- New results on induced matchings
- On Hamiltonicity of \{claw, net\}-free graphs
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Linear Time Algorithms for Hamiltonian Problems on (Claw,Net)-Free Graphs
- Representation of a finite graph by a set of intervals on the real line
- Stability in circular arc graphs
- Graph Classes: A Survey
- Independent Sets in Asteroidal Triple-Free Graphs
- Bipartite Domination and Simultaneous Matroid Covers
- Induced matchings in cubic graphs
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Independent Sets of Maximum Weight in Apple-Free Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On distance-3 matchings and induced matchings
