Recognizing binet matrices

• 成果类型: Article
• 署名作者: Musitelli, Antoine
• 署名单位: University of Padua
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0372-8
• 发表日期: 2010
• 页码: 349-381
• 关键词: orientation

摘要

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 billet matrices called bicyclic and cyclic.