کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419498 | 683823 | 2011 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Characterization and representation problems for intersection betweennesses Characterization and representation problems for intersection betweennesses](/preview/png/419498.png)
For a set system M=(Mv)v∈VM=(Mv)v∈V indexed by the elements of a finite set VV, the intersection betweenness B(M)B(M) induced by MM consists of all triples (u,v,w)∈V3(u,v,w)∈V3 with Mu∩Mw⊆MvMu∩Mw⊆Mv. Similarly, the strict intersection betweenness Bs(M)Bs(M) induced by MM consists of all triples (u,v,w)∈B(M)(u,v,w)∈B(M) such that uu, vv, and ww are pairwise distinct. The notion of a strict intersection betweenness was introduced by Burigana [L. Burigana, Tree representations of betweenness relations defined by intersection and inclusion, Math. Soc. Sci. 185 (2009) 5–36]. We provide axiomatic characterizations of intersection betweennesses and strict intersection betweennesses. Our results yield a simple and efficient algorithm that constructs a representing set system for a given (strict) intersection betweenness. We study graphs whose strict shortest path betweenness is a strict intersection betweenness. Finally, we explain how the algorithmic problem related to Burigana’s notion of a partial tree representation can be solved efficiently using well-known algorithms.
Journal: Discrete Applied Mathematics - Volume 159, Issue 5, 6 March 2011, Pages 389–395