Generalizing the induced matching by edge capacity constraints

DOI10.1016/J.DISOPT.2006.11.004zbMATH Open1163.90606OpenAlexW2015510928MaRDI QIDQ2467130FDOQ2467130

Hiroshi Nagamochi, Takuro Fukunaga

Publication date: 18 January 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2006.11.004

zbMATH Keywords

approximation algorithminduced matchingpolytopesedge capacity

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Cites Work

• Title not available (Why is that?)
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Induced matchings
• On maximum induced matchings in bipartite graphs
• Edge Dominating Sets in Graphs
• A polynomial algorithm for b-matchings: An alternative approach
• Minimum Edge Dominating Sets
• Title not available (Why is that?)
• NP-completeness of some generalizations of the maximum matching problem
• 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
• Title not available (Why is that?)
• On the approximability of the maximum induced matching problem
• New results on induced matchings
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
• Approximating the tree and tour covers of a graph
• Irredundancy in circular arc graphs
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Approximability of the capacitated \(b\)-edge dominating set problem
• Title not available (Why is that?)
• Algorithms and Computation

Cited In (1)

• Approximating weighted induced matchings

   Recommendations

• Approximating weighted induced matchings 👍 👎
• Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier 👍 👎
• Maximum weight induced matching in some subclasses of bipartite graphs 👍 👎
• A Linear Algorithm for Computing of a Minimum Weight Maximal Induced Matching in an Edge-Weighted Tree 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Generalizing the induced matching by edge capacity constraints

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