Navegar

Colección

Datos Estadísticas

Artículo

El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

An induced matching is a matching where no two edges are connected by a third edge. Finding a maximum induced matching on graphs with maximum degree Δ for Δ≥3, is known to be NP-complete. In this work we consider the weighted version of this problem, which has not been extensively studied in the literature. We devise an almost tight fractional local ratio algorithm with approximation ratio Δ which proves to be effective also in practice. Furthermore, we show that a simple greedy algorithm applied to K1,k-free graphs yields an approximation ratio 2k−3. We explore the behavior of this algorithm on subclasses of chair-free graphs and we show that it yields an approximation ratio k when restricted to (K1,k,chair)-free graphs. © 2018 Elsevier B.V.

Registro:

Documento: Artículo
Título:Approximating weighted induced matchings
Autor:Lin, M.C.; Mestre, J.; Vasiliev, S.
Filiación:CONICET and Instituto de Cálculo, FCEyN, Universidad de Buenos Aires, Argentina
The University Of Sydney, Australia
Palabras clave:Approximation algorithms; Maximum induced matching; Graphic methods; Approximation ratios; Fractional local ratio; Free graphs; Greedy algorithms; Induced matchings; Maximum degree; Maximum induced matchings; NP Complete; Approximation algorithms
Año:2018
Volumen:243
Página de inicio:304
Página de fin:310
DOI: http://dx.doi.org/10.1016/j.dam.2018.01.009
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v243_n_p304_Lin

Referencias:

  • Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D., Local ratio: A unified framework for approximation algorithms - In memoriam: Shimon Even 1935-2004 (2004) ACM Comput. Surv., 36 (4), pp. 422-463
  • Brandstdt, A., Mosca, R., On distance-3 matchings and induced matchings (2011) Discrete Appl. Math., 159 (7), pp. 509-520
  • Cameron, K., Induced matchings (1989) Discrete Appl. Math., 24 (1), pp. 97-102
  • Cameron, K., Induced matchings in intersection graphs (2004) Discrete Math., 278 (1-3), pp. 1-9
  • Cameron, K., Sritharan, R., Tang, Y., Finding a maximum induced matching in weakly chordal graphs (2003) Discrete Math., 266 (1-3), pp. 133-142
  • Cameron, K., Walker, T., The graphs with maximum induced matching and maximum matching the same size (2005) Discrete Math., 299 (1-3), pp. 49-55
  • Canzar, S., Elbassioni, K.M., Klau, G.W., Mestre, J., On tree-constrained matchings and generalizations (2015) Algorithmica, 71 (1), pp. 98-119
  • Chang, J.-M., Induced matchings in asteroidal triple-free graphs (2003) Discrete Appl. Math., 132 (1-3), pp. 67-78
  • Dabrowski, K.K., Demange, M., Lozin, V.V., New results on maximum induced matchings in bipartite graphs and beyond (2013) Theoret. Comput. Sci., 478, pp. 33-40
  • Duarte, M.A., Joos, F., Penso, L.D., Rautenbach, D., Souza, U.S., Maximum induced matchings close to maximum matchings (2015) Theoret. Comput. Sci., 588, pp. 131-137
  • Duckworth, W., Manlove, D.F., Zito, M., On the approximability of the maximum induced matching problem (2005) J. Discrete Algorithms, 3 (1), pp. 79-91
  • Fricke, G., Laskar, R., Strong matchings on trees (1992) Congr. Numer., 89, pp. 239-243
  • Fukunaga, T., Nagamochi, H., Generalizing the induced matching by edge capacity constraints (2007) Discrete Optim., 4 (2), pp. 198-205
  • Golumbic, M.C., Laskar, R.C., Irredundancy in circular arc graphs (1993) Discrete Appl. Math., 44 (1), pp. 79-89
  • Golumbic, M.C., Lewenstein, M., New results on induced matchings (2000) Discrete Appl. Math., 101 (1-3), pp. 157-165
  • Gotthilf, Z., Lewenstein, M., Tighter approximations for maximum induced matchings in regular graphs (2006) WAOA, Lecture Notes in Comput. Sci., 3879, pp. 270-281. , Erlebach T. Persinao G. Springer
  • Henning, M.A., Rautenbach, D., Induced matchings in subcubic graphs without short cycles (2014) Discrete Math., 315-316, pp. 165-172
  • Joos, F., Induced matchings in graphs of bounded maximum degree (2016) SIAM J. Discrete Math., 30 (3), pp. 1876-1882
  • Joos, F., Nguyen, V.H., Induced matchings in graphs of degree at most 4 (2016) SIAM J. Discrete Math., 30 (1), pp. 154-165
  • Joos, F., Rautenbach, D., Sasse, T., Induced matchings in subcubic graphs (2014) SIAM J. Discrete Math., 28 (1), pp. 468-473
  • Kang, R.J., Mnich, M., Müller, T., Induced matchings in subcubic planar graphs (2012) SIAM J. Discrete Math., 26 (3), pp. 1383-1411
  • Ko, C.W., Shepherd, F.B., (1994), Adding an identity to a totally unimodular matrix, Working Paper LSEOR.94.14 London School of Economics, Operational Research Group; Kobler, D., Rotics, U., Finding maximum induced matchings in subclasses of claw-free and P5-free graphs, and in graphs with matching and induced matching of equal maximum size (2003) Algorithmica, 37 (4), pp. 327-346
  • Krishnamurthy, C.M., Sritharan, R., Maximum induced matching problem on hhd-free graphs (2012) Discrete Appl. Math., 160 (3), pp. 224-230
  • Lokshantov, D., Vatshelle, M., Villanger, Y., Independent set in P5-free graphs in polynomial time (2014) SODA, pp. 570-581. , SIAM
  • Lozin, V., On maximum induced matchings in bipartite graphs (2002) Inf. Process. Lett., 81 (1), pp. 7-11
  • Moser, H., Sikdar, S., The parameterized complexity of the induced matching problem (2009) Discrete Appl. Math., 157 (4), pp. 715-727
  • Orlovich, Y., Finke, G., Gordon, V., Zverovich, I., Approximability results for the maximum and minimum maximal induced matching problems (2008) Discrete Optim., 5 (3), pp. 584-593
  • Rautenbach, D., Two greedy consequences for maximum induced matchings (2015) Theoret. Comput. Sci., 602, pp. 32-38
  • Stockmeyer, L.J., Vazirani, V.V., NP-completeness of some generalizations of the maximum matching problem (1982) Inf. Process. Lett., 15 (1), pp. 14-19
  • Takaoka, A., Tayu, S., Ueno, S., Weighted dominating sets and induced matchings in orthogonal ray graphs (2014) Proceedings of CoDIT, pp. 69-73
  • Zito, M., Induced matchings in regular graphs and trees (1999) WG, Lecture Notes in Comput. Sci., 1665, pp. 89-101. , Widmayer P. Neyer G. Eidenbenz S. Springer

Citas:

---------- APA ----------
Lin, M.C., Mestre, J. & Vasiliev, S. (2018) . Approximating weighted induced matchings. Discrete Applied Mathematics, 243, 304-310.
http://dx.doi.org/10.1016/j.dam.2018.01.009
---------- CHICAGO ----------
Lin, M.C., Mestre, J., Vasiliev, S. "Approximating weighted induced matchings" . Discrete Applied Mathematics 243 (2018) : 304-310.
http://dx.doi.org/10.1016/j.dam.2018.01.009
---------- MLA ----------
Lin, M.C., Mestre, J., Vasiliev, S. "Approximating weighted induced matchings" . Discrete Applied Mathematics, vol. 243, 2018, pp. 304-310.
http://dx.doi.org/10.1016/j.dam.2018.01.009
---------- VANCOUVER ----------
Lin, M.C., Mestre, J., Vasiliev, S. Approximating weighted induced matchings. Discrete Appl Math. 2018;243:304-310.
http://dx.doi.org/10.1016/j.dam.2018.01.009