dc.creator | Castro Ochoa, Natalia de | es |
dc.creator | Garrido Vizuete, María de los Angeles | es |
dc.creator | Robles Arias, Rafael | es |
dc.creator | Villar Liñán, María Trinidad | es |
dc.date.accessioned | 2023-09-21T06:15:53Z | |
dc.date.available | 2023-09-21T06:15:53Z | |
dc.date.issued | 2023-05 | |
dc.identifier.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. | |
dc.identifier.issn | 1572-5286 | es |
dc.identifier.issn | 1873-636X | es |
dc.identifier.uri | https://hdl.handle.net/11441/149060 | |
dc.description.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 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. | es |
dc.format | application/pdf | es |
dc.format.extent | 15 p. | es |
dc.language.iso | eng | es |
dc.publisher | Elsevier | es |
dc.relation.ispartof | Discrete Optimization, 48 (100773). | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Graph colouring | es |
dc.subject | Greyscale | es |
dc.subject | Minimum gradation | es |
dc.subject | Graph algorithms | es |
dc.title | Minimum gradation in greyscales of graphs | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Geometría y Topología | es |
dc.relation.projectID | MTM2015-65397-P | es |
dc.relation.projectID | PAI FQM-164 | es |
dc.relation.projectID | PAI FQM-326 | es |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S1572528623000154?via%3Dihub | es |
dc.identifier.doi | 10.1016/j.disopt.2023.100773 | es |
dc.contributor.group | Universidad de Sevilla. FQM164: Matemática Discreta: Teoría de Grafos y Geometría Computacional | es |
dc.contributor.group | Universidad de Sevilla. FQM326: Geometría diferencial y Teoría de Lie | es |
dc.journaltitle | Discrete Optimization | es |
dc.publication.volumen | 48 | es |
dc.publication.issue | 100773 | es |
dc.contributor.funder | Ministerio de Ciencia e Innovación (MICIN). España | es |
dc.contributor.funder | Junta de Andalucía | es |