Premium
A bidirected generalization of network matrices
Author(s) -
Appa Gautam,
Kotnyek Balázs
Publication year - 2006
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20108
Subject(s) - unimodular matrix , generalization , mathematics , incidence matrix , combinatorics , constraint (computer aided design) , discrete mathematics , computer science , node (physics) , mathematical analysis , geometry , structural engineering , engineering
We define binet matrices, which furnish a direct generalization of totally unimodular network matrices and arise from the node‐edge incidence matrices of bidirected graphs in the same way as network matrices do from directed graphs. We develop the necessary theory, give binet representations for interesting sets of matrices, characterize totally unimodular binet matrices and discuss the recognition problem. We also prove that binet constraint matrices guarantee half‐integral optimal solutions to linear programs. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 185–198 2006