Article
The minimum maximal k-partial-matching problem
Author/s | García Vargas, Ignacio
Senhadji Navarro, Raouf |
Department | Universidad de Sevilla. Departamento de Arquitectura y Tecnología de Computadores |
Publication Date | 2013 |
Deposit Date | 2019-12-10 |
Published in |
|
Abstract | 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. |
Citation | García Vargas, I. y Senhadji Navarro, R. (2013). The minimum maximal k-partial-matching problem. Optimization letters, 7 (8), 1959-1968. |
Files | Size | Format | View | Description |
---|---|---|---|---|
The minimum maximal k-partial- ... | 249.6Kb | [PDF] | View/ | |