Generalizing the induced matching by edge capacity constraints

Anstee, 1987, A polynomial algorithm for b-matchings: An alternative approach, Information Processing Letters, 24, 153, 10.1016/0020-0190(87)90178-5 Arkin, 1993, Approximating the tree and tour covers of a graph, Information Processing Letters, 47, 275, 10.1016/0020-0190(93)90072-H A. Berger, T. Fukunaga, H. Nagamochi, O. Parekh, Capacitated b-edge dominating set and related problems (submitted for publication) Cameron, 1989, Induced matchings, Discrete Applied Mathematics, 24, 97, 10.1016/0166-218X(92)90275-F Carr, 2001, A 2110-approximation algorithm for a generalization of the weighted edge-dominating set problem, Journal of Combinatorial Optimization, 5, 317, 10.1023/A:1011445210568 M. Chlebík, J. Chlebíková, Approximation hardness of minimum edge dominating set and minimum maximal matching, in: Proceedings of the 14th Annual International Symposium on Algorithms and Computation, ISAAC2003, 2003, pp. 415–424 Duckworth, 2005, On the approximability of the maximum induced matching problem, Journal of Discrete Algorithms, 3, 79, 10.1016/j.jda.2004.05.001 Fujito, 2002, A 2-approximation algorithm for the minimum weight edge dominating set problem, Discrete Applied Mathematics, 118, 199, 10.1016/S0166-218X(00)00383-8 Garey, 1979 Golumbic, 1993, Irredundancy in circular arc graphs, Discrete Applied Mathematics, 44, 79, 10.1016/0166-218X(93)90223-B Golumbic, 2000, New results on induced matchings, Discrete Applied Mathematics, 101, 157, 10.1016/S0166-218X(99)00194-8 Håstad, 1999, Clique is hard to approximate within n1−ε, Acta Mathematica, 182, 105, 10.1007/BF02392825 Horton, 1993, Minimum edge dominating sets, SIAM Journal on Discrete Mathematics, 6, 375, 10.1137/0406030 Kobler, 2003, Finding maximum induced matchings in subclasses of clawfree and p5-free graphs, and in graphs with matching and induced matching of equal maximum size, Algorithmica, 37, 327, 10.1007/s00453-003-1035-4 Lozin, 2002, On maximum induced matchings in bipartite graphs, Information Processing Letters, 81, 7, 10.1016/S0020-0190(01)00185-5 S. Mitchell, S. Hedetniemi, Edge domination in trees, in: Proceedings of 8th Southeastern Conference on Combinatorics, Graph Theory, and Computing, 1977, pp. 489–509 O. Parekh, Edge dominating and hypomatchable sets, in: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 287–291 Salavatipour, 2004, A polynomial time algorithm for strong edge coloring of partial k-trees, Discrete Applied Mathematics, 143, 285, 10.1016/j.dam.2004.03.001 Schrijver, 2003 Srinivasan, 1995, Edge domination on bipartite permutation graphs and contriangulated graphs, Information Processing Letters, 56, 165, 10.1016/0020-0190(95)94093-8 Stockmeyer, 1982, NP-completeness of some generalizations of the maximum matching problem, Information Processing Letters, 15, 14, 10.1016/0020-0190(82)90077-1 Yannakakis, 1980, Edge dominating sets in graphs, SIAM Journal on Applied Mathematics, 38, 364, 10.1137/0138030 Zito, 1999, Maximum induced matchings in regular graphs and trees, vol. 1665, 89