Name
Abstract | ||
|---|---|---|
In a bidirected graph, each end of each edge is independently oriented. We show how to express any column of the incidence matrix as a half-integral linear combination of any column basis, through a simplification, based on an idea of Bolker, of a combinatorial algorithm of Appa and Kotnyek. Corollaries are that the inverse of each nonsingular square submatrix has entries 0, $\pm{1\over 2}$, and ±1, and that a bidirected integral linear program has half-integral solutions. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 36–38 2006Mathematics Subject Classifications (2000): Primary 05C22; Secondary 05B35; 05C20; 90C10 |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1002/net.v48:1 | Networks |
Keywords | Field | DocType |
linear program,network programming,incidence matrix,bidirected graph | Discrete mathematics,Linear combination,Inverse,Mathematical optimization,Combinatorics,Bidirected graph,Linear programming,Invertible matrix,SIMPLE algorithm,Mathematics,Incidence matrix,Computer network programming | Journal |
Volume | Issue | ISSN |
48 | 1 | 0028-3045 |
Citations | PageRank | References |
7 | 0.58 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ethan D Bolker | 1 | 23 | 4.94 |
| T. Zaslavsky | 2 | 297 | 56.67 |