Navegar

Colección

Datos Estadísticas

Artículo

Lin, M.C.; Mizrahi, M.J.; Szwarcfiter, J.L. "An O*(1.1939n) time algorithm for minimum weighted dominating induced matching" (2013) 24th International Symposium on Algorithms and Computation, ISAAC 2013. 8283 LNCS:558-567
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:

Say that an edge of a graph G dominates itself and every other edge sharing a vertex of it. An edge dominating set of a graph G = (V,E) is a subset of edges E′ ⊆ E which dominates all edges of G. In particular, if every edge of G is dominated by exactly one edge of E′ then E′ is a dominating induced matching. It is known that not every graph admits a dominating induced matching, while the problem to decide if it does admit it is NP-complete. In this paper we consider the problems of finding a minimum weighted dominating induced matching, if any, and counting the number of dominating induced matchings of a graph with weighted edges. We describe an exact algorithm for general graphs that runs in O*(1.1939 n) time and polynomial (linear) space, for solving these problems. This improves over the existing exact algorithms for the problems in consideration. © 2013 Springer-Verlag.

Registro:

Documento: Artículo
Título:An O*(1.1939n) time algorithm for minimum weighted dominating induced matching
Autor:Lin, M.C.; Mizrahi, M.J.; Szwarcfiter, J.L.
Ciudad:Hong Kong
Filiación:Instituto de Cálculo, Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
COPPE, Universidade Federal Do Rio de Janeiro, Instituto Nacional de Metrologia, Qualidade e Tecnologia, Rio de Janeiro, Brazil
Palabras clave:branch & reduce; dominating induced matchings; exact algorithms; Edge dominating set; Edge sharing; Exact algorithms; General graph; Graph G; Induced matchings; NP Complete; Time algorithms; Algorithms; Graph theory; Problem solving
Año:2013
Volumen:8283 LNCS
Página de inicio:558
Página de fin:567
DOI: http://dx.doi.org/10.1007/978-3-642-45030-3_52
Título revista:24th International Symposium on Algorithms and Computation, ISAAC 2013
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8283LNCS_n_p558_Lin

Referencias:

  • Bjorklund, A., Determinant sums for undirected hamiltonicity (2010) Annual Symposium on Foundations of Computer Science, FOCS 2010, pp. 173-182
  • Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M., Fourier meets möbius: Fast subset convolution (2007) Annual Symposium on Foundations of Computer Science, STOC 2007, pp. 67-74
  • Brandstädt, A., Hundt, C., Nevries, R., Efficient edge domination on hole-free graphs in polynomial time (2010) LNCS, 6034, pp. 650-661. , López-Ortiz, A. (ed.) LATIN 2010. Springer, Heidelberg
  • Brandstädt, A., Leitert, A., Rautenbach, D., Efficient dominating and edge dominating sets for graphs and hypergraphs (2012) LNCS, 7676, pp. 267-277. , Chao, K.-M., Hsu, T.-S., Lee, D.-T. (eds.) ISAAC 2012. Springer, Heidelberg
  • Brandstädt, A., Mosca, R., Dominating Induced Matchings for P7-free Graphs in Linear Time (2011) LNCS, 7074, pp. 100-109. , Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. Springer, Heidelberg
  • Brandstädt, A., Lozin, V.V., On the linear structure and clique-width of bipartite permutation graphs (2003) Ars Combinatoria, 67, pp. 273-281
  • Cardoso, D.M., Korpelainen, N., Lozin, V.V., On the complexity of the dominating induced matching problem in hereditary classes of graphs (2011) Discrete Applied Mathematics, 159, pp. 21-531
  • Cardoso, D.M., Lozin, V.V., Dominating induced matchings (2009) LNCS, 5420, pp. 77-86. , Lipshteyn, M., Levit, V.E., McConnell, R.M. (eds.) Graph Theory, Computational Intelligence and Thought. Springer, Heidelberg
  • Cardoso, D.M., Cerdeira, J.O., Delorme, C., Silva, P.C., Efficient edge domination in regular graphs (2008) Discrete Applied Mathematics, 156, pp. 3060-3065
  • Dahllöf, V., Jonsson, P., Wahlström, M., Counting models for 2sat and 3sat formulae (2005) Theoretical Computer Science, 332, pp. 265-291
  • Dahllöf, V., Jonsson, P., An algorithm for counting maximum weighted independent sets and its applications (2002) ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, pp. 292-298
  • Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A., On two techniques of combining branching and treewidth (2009) Algorithmica, 54, pp. 181-207
  • Fomin, F.V., Grandoni, F., Kratsch, D., Measure and conquer: A simple O* (1.220n) independent set algorithm (2006) SODA 2006 ACM-SIAM Symposium on Discrete Algorithms, pp. 18-25
  • Fomin, F.V., Kratsch, D., Exact Exponential Algorithms (2010) EATCS Series in Theoretical Computer Science, , Springer, Berlin
  • Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holmes, N.D., Efficient edge domination problems in graphs (1993) Information Processing Letters, 48, pp. 221-228
  • Gupta, S., Raman, V., Saurabh, S., Maximum r-regular induced subgraph problem: Fast exponential algorithms and combinatorial bounds (2012) SIAM Journal on Discrete Mathematics, 26, pp. 1758-1780
  • Korpelainen, N., A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs (2009) Electronic Notes in Discrete Mathematics, 32, pp. 133-140
  • Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., Exact algorithms for dominating induced matchings (2013) CoRR, , abs/1301.7602
  • Livingston, M., Stout, Q.F., Distributing resources in hypercube computers (1988) C3P Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, 1, pp. 222-231. , ACM
  • Lu, C.L., Ko, M.-T., Tang, C.Y., Perfect edge domination and efficient edge domination in graphs (2002) Discrete Applied Mathematics, 119, pp. 227-250
  • Lu, C.L., Tang, C.Y., Solving the weighted efficient edge domination problem on bipartite permutation graphs (1998) Discrete Applied Mathematics, 87, pp. 203-211
  • Milanic, M., Hereditary efficiently dominatable graphs (2013) Journal of Graph Theory, 73, pp. 400-424
  • Van Rooij, J.M.M., Nederlof, J., Van Dijk, T.C., Inclusion/exclusion meets measure and conquer (2009) LNCS, 5757, pp. 554-565. , Fiat, A., Sanders, P. (eds.) ESA 2009. Springer, Heidelberg
  • Wahlström, M., A tighter bound for counting max-weight solutions to 2SAT instances (2008) LNCS, 5018, pp. 202-213. , Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. Springer, Heidelberg
  • Woeginger, G.J., Exact algorithms for NP-hard problems: A survey (2003) Combinatorial Optimization - Eureka, You Shrink!, pp. 185-207. , Springer-Verlag New York, Inc., New York

Citas:

---------- APA ----------
Lin, M.C., Mizrahi, M.J. & Szwarcfiter, J.L. (2013) . An O*(1.1939n) time algorithm for minimum weighted dominating induced matching. 24th International Symposium on Algorithms and Computation, ISAAC 2013, 8283 LNCS, 558-567.
http://dx.doi.org/10.1007/978-3-642-45030-3_52
---------- CHICAGO ----------
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L. "An O*(1.1939n) time algorithm for minimum weighted dominating induced matching" . 24th International Symposium on Algorithms and Computation, ISAAC 2013 8283 LNCS (2013) : 558-567.
http://dx.doi.org/10.1007/978-3-642-45030-3_52
---------- MLA ----------
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L. "An O*(1.1939n) time algorithm for minimum weighted dominating induced matching" . 24th International Symposium on Algorithms and Computation, ISAAC 2013, vol. 8283 LNCS, 2013, pp. 558-567.
http://dx.doi.org/10.1007/978-3-642-45030-3_52
---------- VANCOUVER ----------
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L. An O*(1.1939n) time algorithm for minimum weighted dominating induced matching. Lect. Notes Comput. Sci. 2013;8283 LNCS:558-567.
http://dx.doi.org/10.1007/978-3-642-45030-3_52