Article
Minimum gradation in greyscales of graphs
Author/s | Castro Ochoa, Natalia de
Garrido Vizuete, María de los Angeles Robles Arias, Rafael Villar Liñán, María Trinidad |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) Universidad de Sevilla. Departamento de Geometría y Topología |
Publication Date | 2023-05 |
Deposit Date | 2023-09-21 |
Published in |
|
Abstract | 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. |
Funding agencies | Ministerio de Ciencia e Innovación (MICIN). España Junta de Andalucía |
Project ID. | MTM2015-65397-P
PAI FQM-164 PAI FQM-326 |
Citation | 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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Minimum gradation in greyscales ... | 833.2Kb | [PDF] | View/ | |