Artículo
Minimum gradation in greyscales of graphs
Autor/es | Castro Ochoa, Natalia de
Garrido Vizuete, María de los Angeles Robles Arias, Rafael Villar Liñán, María Trinidad |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) Universidad de Sevilla. Departamento de Geometría y Topología |
Fecha de publicación | 2023-05 |
Fecha de depósito | 2023-09-21 |
Publicado en |
|
Resumen | In this paper we present the notion of greyscale of a graph as a colouring of its vertices that uses colours from the real interval [0,1]. Any greyscale induces another colouring by assigning to each edge the non-negative ... In this paper we present the notion of greyscale of a graph as a colouring of its vertices that uses colours from the real interval [0,1]. Any greyscale induces another colouring by assigning to each edge the non-negative difference between the colours of its vertices. These edge colours are ordered in lexicographical decreasing ordering and give rise to a new element of the graph: the gradation vector. We introduce the notion of minimum gradation vector as a new invariant for the graph and give polynomial algorithms to obtain it. These algorithms also output all greyscales that produce the minimum gradation vector. This way we tackle and solve a novel vectorial optimization problem in graphs that may generate more satisfactory solutions than those generated by known scalar optimization approaches. |
Agencias financiadoras | Ministerio de Ciencia e Innovación (MICIN). España Junta de Andalucía |
Identificador del proyecto | MTM2015-65397-P
PAI FQM-164 PAI FQM-326 |
Cita | Castro Ochoa, N.d., Garrido Vizuete, M.d.l.A., Robles Arias, R. y Villar Liñán, M.T. (2023). Minimum gradation in greyscales of graphs. Discrete Optimization, 48 (100773). https://doi.org/10.1016/j.disopt.2023.100773. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Minimum gradation in greyscales ... | 833.2Kb | [PDF] | Ver/ | |