Exact Algorithms for Minimum Weighted Dominating Induced Matching

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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Publicado:	2017
Materias:	Dominating induced matchings Exact algorithms Graph theory Algorithms Polynomial approximation Polynomials Problem solving Dominating sets Edge dominating set General graph Induced matchings Maximal independent set Polynomial number Polynomial-time
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v77_n3_p642_Lin http://hdl.handle.net/20.500.12110/paper_01784617_v77_n3_p642_Lin
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_01784617_v77_n3_p642_Lin
record_format	dspace
spelling	paper:paper_01784617_v77_n3_p642_Lin2023-06-08T15:19:18Z Exact Algorithms for Minimum Weighted Dominating Induced Matching Dominating induced matchings Exact algorithms Graph theory Algorithms Polynomial approximation Polynomials Problem solving Dominating sets Edge dominating set Exact algorithms General graph Induced matchings Maximal independent set Polynomial number Polynomial-time Graph theory 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 counting the number of dominating induced matchings and finding a minimum weighted dominating induced matching, if any, of a graph with weighted edges. We describe three exact algorithms for general graphs. The first runs in linear time for a given vertex dominating set of fixed size of the graph. The second runs in polynomial time if the graph admits a polynomial number of maximal independent sets. The third one is an O∗(1. 1939 n) time and polynomial (linear) space, which improves over the existing algorithms for exactly solving this problem in general graphs. © 2015, Springer Science+Business Media New York. 2017 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v77_n3_p642_Lin http://hdl.handle.net/20.500.12110/paper_01784617_v77_n3_p642_Lin
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Dominating induced matchings Exact algorithms Graph theory Algorithms Polynomial approximation Polynomials Problem solving Dominating sets Edge dominating set Exact algorithms General graph Induced matchings Maximal independent set Polynomial number Polynomial-time Graph theory
spellingShingle	Dominating induced matchings Exact algorithms Graph theory Algorithms Polynomial approximation Polynomials Problem solving Dominating sets Edge dominating set Exact algorithms General graph Induced matchings Maximal independent set Polynomial number Polynomial-time Graph theory Exact Algorithms for Minimum Weighted Dominating Induced Matching
topic_facet	Dominating induced matchings Exact algorithms Graph theory Algorithms Polynomial approximation Polynomials Problem solving Dominating sets Edge dominating set Exact algorithms General graph Induced matchings Maximal independent set Polynomial number Polynomial-time Graph theory
description	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 counting the number of dominating induced matchings and finding a minimum weighted dominating induced matching, if any, of a graph with weighted edges. We describe three exact algorithms for general graphs. The first runs in linear time for a given vertex dominating set of fixed size of the graph. The second runs in polynomial time if the graph admits a polynomial number of maximal independent sets. The third one is an O∗(1. 1939 n) time and polynomial (linear) space, which improves over the existing algorithms for exactly solving this problem in general graphs. © 2015, Springer Science+Business Media New York.
title	Exact Algorithms for Minimum Weighted Dominating Induced Matching
title_short	Exact Algorithms for Minimum Weighted Dominating Induced Matching
title_full	Exact Algorithms for Minimum Weighted Dominating Induced Matching
title_fullStr	Exact Algorithms for Minimum Weighted Dominating Induced Matching
title_full_unstemmed	Exact Algorithms for Minimum Weighted Dominating Induced Matching
title_sort	exact algorithms for minimum weighted dominating induced matching
publishDate	2017
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v77_n3_p642_Lin http://hdl.handle.net/20.500.12110/paper_01784617_v77_n3_p642_Lin
_version_	1768546296697716736

Exact Algorithms for Minimum Weighted Dominating Induced Matching

Ejemplares similares