The Minimum Clique Routing Problem on Cycles | ||
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Universidad de Chile. | |
| dc.conicet.organizacion | Universidad de Chile. | |
| dc.conicet.organizacion | Escuela Politécnica Nacional | |
| dc.contributor.author | Escalante, Mariana Silvina | |
| dc.contributor.author | Tolomei, Paola Beatriz | |
| dc.contributor.author | Matamala, M. | |
| dc.contributor.author | Rapaport, I. | |
| dc.contributor.author | Torres, L. M. | |
| dc.date.issued | 2025-03 | |
| dc.description.abstract | In the minimum clique routing problem on cycles mcrpc, we are given a cycle together with a set of demands (weighted terminals pairs) and the goal is to route all the pairs minimizing the maximum weight clique of the intersection graph induced by the routing. The nodes of this graph are the demands with their corresponding weights and two demands are adjacent when their routes share at least one arc. In this work, we are not only interested in the mcrpc but also in two natural subproblems. First, we consider the situation where the demands are disjoint, in the sense that every two demands do not share any of their corresponding terminals. Second, we analyze the subproblem where the weights of the routes are all equal. We first show that the problem is NP-hard even in the subproblem of disjoint demands. For the case of arbitrary weights, we exhibit a simple combinatorial 2-approximation algorithm and a 3/2-approximation algorithm based on rounding a solution of a relaxation of an integer linear programming formulation of our problem. Finally, we give a fixed parameter tractable algorithm for the case of uniform weights, whose parameter is the maximum number of demands for which a demand exists whose terminals alternate in the cycle with the terminals of each of them. | es |
| dc.description.fil | Fil: Escalante, Mariana Silvina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina | |
| dc.description.fil | Fil: Tolomei, Paola Beatriz. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina | |
| dc.description.fil | Fil: Matamala, M.. Universidad de Chile.; Chile | |
| dc.description.fil | Fil: Rapaport, I.. Universidad de Chile.; Chile | |
| dc.description.fil | Fil: Torres, L. M.. Escuela Politécnica Nacional; Ecuador | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Escalante, Mariana Silvina; Tolomei, Paola Beatriz; Matamala, M.; Rapaport, I.; Torres, L. M.; The Minimum Clique Routing Problem on Cycles; John Wiley & Sons; Networks; 86; 1; 3-2025; 71-79 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0028-3045 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/274515 | |
| dc.journal.number | 1 | es |
| dc.journal.pagination | 71-79 | es |
| dc.journal.pais | Estados Unidos | es |
| dc.journal.title | Networks | es |
| dc.journal.volume | 86 | es |
| dc.language.iso | eng | es |
| dc.publisher | John Wiley & Sons | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://onlinelibrary.wiley.com/doi/10.1002/net.22277 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1002/net.22277 | |
| dc.rights | info:eu-repo/semantics/restrictedAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | ROUTING PROBLEM | es |
| dc.subject | RING NETWORKS | es |
| dc.subject | APPROXIMATION ALGORITHM | es |
| dc.subject | MINIMUM CLIQUE | es |
| dc.subject.classification | Otras Matemáticas | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | The Minimum Clique Routing Problem on Cycles | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.909c9aff-3d62-4a62-baa9-80a3ef797ea3_B.pdf
- Tamaño:
- 358.41 KB
- Formato:
- Adobe Portable Document Format