ON THE RECOGNITION OF PERMUTED SUPNICK AND INCOMPLETE MONGE MATRICES

Authors
DEINEKO V RUDOLF R WOEGINGER GJ
Citation
V. Deineko et al., ON THE RECOGNITION OF PERMUTED SUPNICK AND INCOMPLETE MONGE MATRICES, Acta informatica, 33(6), 1996, pp. 559-569
Citations number
13
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Acta informatica → ACNP
ISSN journal
00015903
Volume
33
Issue
6
Year of publication
1996
Pages
559 - 569
Database
ISI
SICI code
0001-5903(1996)33:6<559:OTROPS>2.0.ZU;2-L
Abstract
Incomplete Monge matrices are a generalization of standard Monge matri ces: the values of some entries are not specified and the Monge proper ty only must hold for all specified entries. We derive several combina torial properties of incomplete Monge matrices and prove that the prob lem of recognizing permuted incomplete Monge matrices is NP-complete. For the special case of permuted Supnick matrices, we derive a fast re cognition algorithm and thereby identify a special case of the n-verte x travelling salesman problem which can be solved in O (n(2) log n) ti me.