Ponencia
On geodesic and monophonic convexity
Autor/es | Hernando Martin, Maria del Carmen
Mora Gine, Mercè Pelayo Melero, Ignacio Manuel Seara Ojea, Carlos |
Fecha de publicación | 2004 |
Fecha de depósito | 2017-03-02 |
Publicado en |
|
Resumen | In this paper we deal with two types of graph convexities, which are the most natural path convexities in a graph and which are defined by a system P of paths in a connected graph G: the geodesic convexity (also called ... In this paper we deal with two types of graph convexities, which are the most natural path convexities in a graph and which are defined by a system P of paths in a connected graph G: the geodesic convexity (also called metric convexity) which arises when we consider shortest paths, and the monophonic convexity (also called minimal path convexity) when we consider chordless paths. First, we present a realization theorem proving, that there is no general relationship between monophonic and geodetic hull sets. Second, we study the contour of a graph, showing that the contour must be monophonic. Finally, we consider the so-called edge Steiner sets. We prove that every edge Steiner set is edge monophonic. |
Identificador del proyecto | MCYT-FEDER TIC- 2001-2171
MCYT-FEDER BFM 2002-0557 2001SGR00224 MCYT BFM2000-1052-C02-01 |
Cita | Hernando Martin, M.d.C., Mora Gine, M., Pelayo Melero, I.M. y Seara Ojea, C. (2004). On geodesic and monophonic convexity. En 20th European Workshop on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
On geodesic and monophonic ... | 113.2Kb | [PDF] | Ver/ | |