Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Counting lines in semi-complete digraphs∗
Indexado
WoS WOS:001198844500041
Scopus SCOPUS_ID:85174408275
DOI 10.1016/J.PROCS.2023.08.247
Año 2023
Tipo proceedings paper

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



A digraph D = (V, A) is semi-complete if for each pair of distinct vertices x and y in V, either xy or yx belong to A. A subset of vertices is a line of D if there are two distinct vertices x and y such that for any vertex z ϵ V, z ϵ if and only if a directed shortest path exists containing x, y and z. A classic result proved by Erdös says that any set of n points in the Euclidean plane endowed with the Euclidean distance defines a metric space with at least n different lines unless there is a line containing the n points. Chen and Chvátal in 2008 conjectured that the same results is true for any metric spaces where lines are defined in a manner similar to above. In this paper we prove that in any semi-complete digraphs with n vertices the number of lines defined by vertices connected by an arc is at least n. Then, the quasi-metric spaces defined by semi-complete digraphs fulfill Chen and Chvátal conjecture in a stronger manner as, on the one hand, they always have at least n lines, and on the other hand, these n lines are defined by vertices at distance one.

Revista



Revista ISSN
Procedia Computer Science 1877-0509

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Sin Disciplinas
Scopus
Computer Science (All)
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 Araujo-Pardo, Gabriela - Universidad Nacional Autónoma de México - México
Univ Nacl Autonoma Mexico - México
2 Matamala, Martín Hombre Universidad de Chile - Chile
3 ZAMORA-PONCE, JOSE TOMAS Hombre Universidad Nacional Andrés Bello - Chile
4 Fernandes, C -
5 Rajsbaum, S -

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
PAPIIT-UNAM
Direccion General de Asuntos del Personal Academico, Universidad Nacional Autonoma de Mexico
MathAmsud
Agencia Nacional de Investigación y Desarrollo
ANID Basal Program

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
✩ Supported by ANID Basal program FB21005, MathAmSud MATH210008 and PAPIIT-UNAM grant IN108121. ✩ Supported by ANID Basal program FB21005, MathAmSud MATH210008 and PAPIIT-UNAM grant IN108121.
Supported by ANID Basal program FB21005, MathAmSud MATH210008 and PAPIIT-UNAM grant IN108121.

Muestra la fuente de financiamiento declarada en la publicación.