Recognizing binet matrices |
| |
Authors: | Antoine Musitelli |
| |
Institution: | 1. Dipartimento di Matematica Pura e Applicata, Universita di Padova, Via Trieste 63, Padova, 35121, Italy
|
| |
Abstract: | Binet matrices generalize network matrices and play an important role in combinatorial optimization. A first polynomial-time algorithm for recognizing binet matrices appeared in the author’s doctoral thesis. In this paper, we present some key ideas and results involved in the design of this algorithm. We show how we can find a Camion basis of the input matrix, whenever this one is binet, and then reduce the recognition problem to that of special binet matrices called bicyclic and cyclic. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|