This paper deals with the reconstruction of binary matrices having specific local constraints, called Timetable Constraints, imposed on their elements. In the first part of the paper, we show that instances of this problem with some fixed parameters are solvable in linear time by means of a greedy approach. In the following, thanks to a slight relaxation of one of the Timetable Constraints, we define a second and more complex greedy algorithm that solves a much wider family of instances. In both of these cases the computational complexity of our algorithms is linear in the dimension of the reconstructed matrix. Finally, we complete the framework by proving that all but one the remaining cases are NP-complete.
Reconstructing binary matrices with timetabling constraints / Brlek, Srecko; Brocchi, Stefano; Frosini, Andrea. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - STAMPA. - 38-41:(2016), pp. 20-31. [10.1016/j.jda.2016.07.001]
Reconstructing binary matrices with timetabling constraints
BROCCHI, STEFANO;FROSINI, ANDREA
2016
Abstract
This paper deals with the reconstruction of binary matrices having specific local constraints, called Timetable Constraints, imposed on their elements. In the first part of the paper, we show that instances of this problem with some fixed parameters are solvable in linear time by means of a greedy approach. In the following, thanks to a slight relaxation of one of the Timetable Constraints, we define a second and more complex greedy algorithm that solves a much wider family of instances. In both of these cases the computational complexity of our algorithms is linear in the dimension of the reconstructed matrix. Finally, we complete the framework by proving that all but one the remaining cases are NP-complete.File | Dimensione | Formato | |
---|---|---|---|
Reconstructing binary matrices.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
420.16 kB
Formato
Adobe PDF
|
420.16 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.