Generalizing the induced matching by edge capacity constraints

DOI10.1016/J.DISOPT.2006.11.004MaRDI QIDQ2467130zbMATH OpenOpenAlexFDO

Authors Takuro Fukunaga, Hiroshi Nagamochi

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)

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
• A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree

Cites work

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

Cited in

(1)

• Approximating weighted induced matchings

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)