Artículo
The minimum maximal k-partial-matching problem
Autor/es | García Vargas, Ignacio
Senhadji Navarro, Raouf |
Departamento | Universidad de Sevilla. Departamento de Arquitectura y Tecnología de Computadores |
Fecha de publicación | 2013 |
Fecha de depósito | 2019-12-10 |
Publicado en |
|
Resumen | In this paper, we introduce a new problem related to bipartite graphs called
minimum maximal k-partial-matching (MMKPM) which has been modelled by
using a relaxation of the concept of matching in a graph. The MMKPM problem ... In this paper, we introduce a new problem related to bipartite graphs called minimum maximal k-partial-matching (MMKPM) which has been modelled by using a relaxation of the concept of matching in a graph. The MMKPM problem can be viewed as a generalization of the classical Hitting Set and Set Cover problems. This property has been used to prove that the MMKPM problem is NPComplete. An integer linear programming formulation and a greedy algorithm have been proposed. The problem can be applied to the design process of finite state machines with input multiplexing for simplifying the complexity of multiplexers. |
Cita | García Vargas, I. y Senhadji Navarro, R. (2013). The minimum maximal k-partial-matching problem. Optimization letters, 7 (8), 1959-1968. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
The minimum maximal k-partial- ... | 249.6Kb | [PDF] | Ver/ | |