An O*(1.1939n) time algorithm 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: 2013
Materias:
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
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8283LNCS_n_p558_Lin
http://hdl.handle.net/20.500.12110/paper_03029743_v8283LNCS_n_p558_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

Ejemplares similares

Ejemplares similares