Mathematics – Combinatorics
Scientific paper
2008-11-10
Mathematics
Combinatorics
17 pages, 3 figures
Scientific paper
A D-polyhedron is a polyhedron $P$ such that if $x,y$ are in $P$ then so are their componentwise max and min. In other words, the point set of a D-polyhedron forms a distributive lattice with the dominance order. We provide a full characterization of the bounding hyperplanes of D-polyhedra. Aside from being a nice combination of geometric and order theoretic concepts, D-polyhedra are a unifying generalization of several distributive lattices which arise from graphs. In fact every D-polyhedron corresponds to a directed graph with arc-parameters, such that every point in the polyhedron corresponds to a vertex potential on the graph. Alternatively, an edge-based description of the point set can be given. The objects in this model are dual to generalized flows, i.e., dual to flows with gains and losses. These models can be specialized to yield some cases of distributive lattices that have been studied previously. Particular specializations are: lattices of flows of planar digraphs (Khuller, Naor and Klein), of $\alpha$-orientations of planar graphs (Felsner), of c-orientations (Propp) and of $\Delta$-bonds of digraphs (Felsner and Knauer). As an additional application we exhibit a distributive lattice structure on generalized flow of breakeven planar digraphs.
Felsner Stefan
Knauer Kolja
No associations
LandOfFree
Distributive Lattices, Polyhedra, and Generalized Flow does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Distributive Lattices, Polyhedra, and Generalized Flow, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributive Lattices, Polyhedra, and Generalized Flow will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-725132