Article ID Journal Published Year Pages File Type
4651315 Discrete Mathematics 2006 5 Pages PDF
Abstract

Let M   be a finite set of vectors in RnRn of cardinality m   and H(M)={{x∈Rn:cTx=0}:c∈M}H(M)={{x∈Rn:cTx=0}:c∈M} the central hyperplane arrangement represented by M. An independent subset of M of cardinality n is called a Camion basis  , if it determines a simplex region in the arrangement H(M)H(M). In this paper, we first present a new characterization of Camion bases, in the case where M   is the column set of the node-edge incidence matrix (without one row) of a given connected digraph. Then, a general characterization of Camion bases as well as a recognition procedure which runs in O(n2m)O(n2m) are given. Finally, an algorithm which finds a Camion basis is presented. For certain classes of matrices, including totally unimodular matrices, it is proven to run in polynomial time and faster than the algorithm due to Fonlupt and Raco.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,