New polynomial-time algorithms for Camion bases

Let M be a finite set of vectors in Rn of cardinality m and 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 arrangementH(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) 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.


Published in:
Discrete Mathematics, 306, 24, 3302-3306
Year:
2006
Keywords:
Note:
PRO 060625
Laboratories:




 Record created 2006-12-15, last modified 2018-01-27

External link:
Download fulltext
n/a
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)