Characterization and representation problems for intersection betweennesses |
| |
Authors: | Dieter Rautenbach,Viní cius Fernandes dos Santos |
| |
Affiliation: | a Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germanyb Instituto de Matemática, NCE, and COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ, Brazil |
| |
Abstract: | For a set system M=(Mv)v∈V indexed by the elements of a finite set V, the intersection betweenness B(M) induced by M consists of all triples (u,v,w)∈V3 with Mu∩Mw⊆Mv. Similarly, the strict intersection betweenness Bs(M) induced by M consists of all triples (u,v,w)∈B(M) such that u, v, and w 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. |
| |
Keywords: | Betweenness Shortest paths Trees |
本文献已被 ScienceDirect 等数据库收录! |
|