DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
Rechercher
(titres de publication, de périodique et noms de colloque inclus)
2007-01-01 - Article/Dans un journal avec peer-review - Anglais - 13 page(s)

Abbas M., Pirlot Marc , Vincke P., "Tangent circle graphs and "orders"" in Discrete Applied Mathematics, 155, 4, 429-441

  • Edition : Elsevier Science, Amsterdam (The Netherlands)
  • Codes CREF : Modèles mathématiques d'aide à la décision (DI1151), Mathématiques (DI1100), Théorie des graphes (DI1146)
  • Unités de recherche UMONS : Mathématique et Recherche opérationnelle (F151)
Texte intégral :

Abstract(s) :

(Anglais) Consider a horizontal line in the plane and let Y(A) be a collection of n circles, possibly of different sizes all tangent to the line on the same side. We define the tangent circle graph associated to Y(A) as the intersection graph of the circles. We also define an irreflexive and asymmetric binary relation P on A; the pair (a,b) representing two circles of Y(A) is in P iff the circle associated to a lies to the right of the circle associated to b and does not intersect it. This defines a new nontransitive preference structure that generalizes the semi-order structure. We study its properties and relationships with other well-known order structures, provide a numerical representation and establish a sufficient condition implying that P is transitive. The tangent circle preference structure offers a geometric interpretation of a model of preference relations defined by means of a numerical representation with multiplicative threshold; this representation has appeared in several recently published papers.

Identifiants :
  • DOI : doi:10.1016/j.dam.2006.09.004