کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421477 | 684491 | 2006 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Two equivalent measures on weighted hypergraphs Two equivalent measures on weighted hypergraphs](/preview/png/421477.png)
Let H=(N,E,w)H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}N={0,1,…,n-1}, a hyperedge set E⊆2NE⊆2N, and real edge-weights w(e)w(e) for e∈Ee∈E. Given a convex n-gon P in the plane with vertices x0,x1,…,xn-1x0,x1,…,xn-1 which are arranged in this order clockwisely, let each node i∈Ni∈N correspond to the vertex xixi and define the area AP(H)AP(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H . For 0⩽i
• cH(i,j,k)⩽cH′(i,j,k)cH(i,j,k)⩽cH′(i,j,k) for all convex three-cuts C(i,j,k)C(i,j,k).From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H′H′ satisfy “AP(H)⩽AP(H′)AP(H)⩽AP(H′) for all convex n-gons P” is immediately obtained.
Journal: Discrete Applied Mathematics - Volume 154, Issue 16, 1 November 2006, Pages 2330–2334