Approximating weighted induced matchings

DOI10.1016/J.DAM.2018.01.009MaRDI QIDQ1752475zbMATH OpenOpenAlexWikidataFDO

Authors 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

zbMATH Keywords

approximation algorithmsmaximum induced matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier
• Approximation and Online Algorithms
• Two greedy consequences for maximum induced matchings
• Locally searching for large induced matchings
• Induced matchings in graphs of bounded maximum degree

Cites work

• scientific article; zbMATH DE number 434499 (Why is no real title available?)
• scientific article; zbMATH DE number 1420901 (Why is no real title available?)
• Approximability results for the maximum and minimum maximal induced matching problems
• Approximation and Online Algorithms
• Finding a maximum induced matching in weakly chordal 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
• Generalizing the induced matching by edge capacity constraints
• Independent set in \(P_5\)-free graphs in polynomial time
• Induced matchings
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in graphs of bounded maximum degree
• Induced matchings in graphs of degree at most 4
• Induced matchings in intersection graphs.
• Induced matchings in subcubic graphs
• Induced matchings in subcubic graphs without short cycles
• Induced matchings in subcubic planar graphs
• Irredundancy in circular arc graphs
• Maximum induced matching problem on hhd-free graphs
• Maximum induced matchings close to maximum matchings
• NP-completeness of some generalizations of the maximum matching problem
• New results on induced matchings
• New results on maximum induced matchings in bipartite graphs and beyond
• On distance-3 matchings and induced matchings
• On maximum induced matchings in bipartite graphs
• On the approximability of the maximum induced matching problem
• On tree-constrained matchings and generalizations
• The graphs with maximum induced matching and maximum matching the same size
• The parameterized complexity of the induced matching problem
• Two greedy consequences for maximum induced matchings

Cited in

(10)

• On the Induced Matching Problem
• scientific article; zbMATH DE number 6866348 (Why is no real title available?)
• Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier
• Approximate Matching in Weighted Sequences
• Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model
• Approximating maximum acyclic matchings by greedy and local search strategies
• Exact algorithms for minimum weighted dominating induced matching
• Generalizing the induced matching by edge capacity constraints
• Weighted restricted 2-matching
• Locally searching for large induced matchings

This page was built for publication: Approximating weighted induced matchings

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