Distributive lattices, polyhedra, and generalized flows
Distributive lattices, polyhedra, and generalized flows
复制标题
DOI：
10.1016/j.ejc.2010.07.011
复制
发表时间：
2011-01-01
影响因子：
1
通讯作者：
Knauer, Kolja
中科院分区：
文献类型：
--
作者：
Felsner, Stefan;Knauer, Kolja
D-多面体是多面体P，如果x，y在P中，那么它们的分支最大值和最小值也是。换言之，D-多面体的点集构成了一个具有支配序的分配格。给出了D-多面体的有界超平面的完整刻画，D-多面体不仅是几何和序论概念的完美结合，而且是图中几个分配格的统一推广。事实上，对于D-多面体，我们将有向图与弧参数相关联，使得多面体中的点对应于图上的顶点势。或者，可以给出D-多面体的点的基于边的描述。在这个模型中，点对应于广义流的对偶，即有收益和有损失的流的对偶。这些模型可以专门用来产生以前研究过的分配格。特殊的专门化是：平面图的流(Khuller，Naor和Klein)，平面图的α方向(Felsner)，c方向(Propp)和有向图的Delta键(Felsner和Knauer)。作为另一个应用，我们证明了盈亏平衡平面有向图的广义流上的分配格结构。(C)2010爱思唯尔有限公司。保留所有权利。
A D-polyhedron is a polyhedron P such that if x, y are in P then so are their componentwise maximums and minimums. 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 with a D-polyhedron we associate a directed graph with arc-parameters, such that points in the polyhedron correspond to vertex potentials on the graph. Alternatively, an edge-based description of the points of a D-polyhedron can be given. In this model the points correspond to the duals of generalized flows, i.e., duals of flows with gains and losses.These models can be specialized to yield distributive lattices that have been previously studied. Particular specializations are: flows of planar digraphs (Khuller, Naor and Klein), alpha-orientations of planar graphs (Felsner), c-orientations (Propp) and Delta-bonds of digraphs (Felsner and Knauer). As an additional application we identify a distributive lattice structure on generalized flow of breakeven planar digraphs. (C) 2010 Elsevier Ltd. All rights reserved.