Metraipolis › archive › dc_9c4e2f7ed11d
Conjunto disjunto máximo — Wikipedia (es)
- Source
- Wikipedia (es)
- Original
- https://es.wikipedia.org/wiki/Conjunto_disjunto_m%C3%A1ximo
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-04T10:49:49.599Z
- SHA-256 of the archived text
9715add4ea3af939a5e6d59355496dca290eda7045093c53ac963ca1df2b90e4- Stable URL of this page
https://metraipolis.com/documento/dc_9c4e2f7ed11d
How to cite
Conjunto disjunto máximo — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Conjunto_disjunto_m%C3%A1ximo (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_9c4e2f7ed11d (Metraipolis archive dc_9c4e2f7ed11d, sha256 9715add4ea3af939a5e6d59355496dca290eda7045093c53ac963ca1df2b90e4)
BibTeX
@misc{dc9c4e2f7ed11d,
title = {Conjunto disjunto máximo — Wikipedia (es)},
howpublished = {Wikipedia (es)},
url = {https://es.wikipedia.org/wiki/Conjunto_disjunto_m%C3%A1ximo},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_9c4e2f7ed11d; sha256 9715add4ea3af939a5e6d59355496dca290eda7045093c53ac963ca1df2b90e4},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Conjunto_disjunto_m%C3%A1ximo. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En geometría computacional, un conjunto disjunto máximo (CDM) es el conjunto más grande de formas geométricas no superpuestas formable a partir de un conjunto dado de formas candidatas. Cada conjunto de formas que no se superponen es un conjunto independiente en el grafo de intersección de las formas. Por lo tanto, el problema del CDM es un caso especial del problema del conjunto independiente máximo (CIM). Ambos problemas son NP-completos, pero encontrar un CDM puede ser más fácil que encontrar un CIM en dos aspectos: Para el problema general del CIM, los algoritmos exactos más conocidos son exponenciales. En cambio, para algunos grafos de intersección geométrica, existen algoritmos subexponenciales para encontrar un CDM. El problema general de encontrar el CIM es difícil de aproximar y ni siquiera tiene una aproximación de factor constante. Para algunos grafos de intersección geométrica, existen esquemas de aproximación de tiempo polinómico (EATPs) para encontrar un CDM. Encontrar un CDM es importante en aplicaciones como asignación automática de etiquetas, diseño de circuitos integrados y multiplexación por división de frecuencia celular. El problema de determinar un CDM se puede generalizar asignando un peso diferente a cada forma y buscando un conjunto disjunto con un peso total máximo. En el siguiente texto, CDM(C) denota el conjunto disjunto máximo de un conjunto C. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in spagnolo, in ordine alfabetico). Fonte: Wikipedia in spagnolo, voce «Conjunto disjunto máximo» — https://es.wikipedia.org/wiki/Conjunto_disjunto_m%C3%A1ximo Wikidata Q17163363: «concept in computational geometry» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q17163363 Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Conjunto_disjunto_m%C3%A1ximo?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 171200101, consultata il 2026-11-04T10:42:33.549Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 0b6131ab3feada32ce98f82e9301ceb70c662ce3535f499cfce60e6c21e74f50