Approximating weighted induced matchings
From MaRDI portal
Publication:1752475
DOI10.1016/j.dam.2018.01.009zbMath1387.05207OpenAlexW2793113890WikidataQ130114584 ScholiaQ130114584MaRDI QIDQ1752475
Min Chih Lin, Julián Mestre, Saveliy Vasiliev
Publication date: 24 May 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2018.01.009
Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (3)
Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model ⋮ Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier ⋮ Approximating maximum acyclic matchings by greedy and local search strategies
Cites Work
- Unnamed Item
- Unnamed Item
- Induced matchings in subcubic graphs without short cycles
- Two greedy consequences for maximum induced matchings
- Irredundancy in circular arc graphs
- On distance-3 matchings and induced matchings
- Maximum induced matching problem on hhd-free graphs
- Approximability results for the maximum and minimum maximal induced matching problems
- The parameterized complexity of the induced matching problem
- NP-completeness of some generalizations of the maximum matching problem
- Induced matchings
- 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
- 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 maximum induced matchings in bipartite graphs and beyond
- New results on induced matchings
- On tree-constrained matchings and generalizations
- Maximum induced matchings close to maximum matchings
- Generalizing the induced matching by edge capacity constraints
- The graphs with maximum induced matching and maximum matching the same size
- Induced Matchings in Graphs of Bounded Maximum Degree
- Induced Matchings in Subcubic Planar Graphs
- Induced Matchings in Subcubic Graphs
- Independent Set in P5-Free Graphs in Polynomial Time
- Induced Matchings in Graphs of Degree at Most 4
- Approximation and Online Algorithms
This page was built for publication: Approximating weighted induced matchings
