Conjunt disjunto màxim
En geometria computacional, un conjunt disjunto màxim (CDM) és el conjunt més gran de formes geomètriques no superpostes formable a partir d'un conjunt donat de formes candidates.

Cada conjunt de formes que no se superponen és un conjunt independent en el grafo d'intersecció de les formes. Per lo tant, el problema del CDM és un cas especial del problema del conjunt independent màxim (CIM). Abdós problemes són NP-complets, pero trobar un CDM pot ser més fàcil que trobar un CIM en dos aspectes:
- Per al problema general de el CIM, els algoritmes exactes més coneguts són exponencials. En canvi, per a alguns grafos d'intersecció geomètrica, existixen algoritmes subexponenciales per a trobar un CDM.[1]
- El problema general de trobar el CIM és difícil d'aproximar i ni tan sols té una aproximació de factor constant. Per a alguns grafos d'intersecció geomètrica, existixen esquemes d'aproximació de temps polinòmic (EATPs) per a trobar un CDM.
Trobar un CDM és important en aplicacions com assignació automàtica d'etiquetes, disseny de circuits integrats i multiplexació per divisió de freqüència celular.
El problema de determinar un CDM es pot generalisar assignant un pes diferent a cada forma i buscant un conjunt disjunto en un pes total màxim.
En el següent text, CDM(C) denota el conjunt disjunto màxim d'un conjunt C.
Algoritmes voraços
Donat un conjunt C de formes, es pot trobar una aproximació a CDM(C) per mig del següent algoritme voraç:
- INICIALIZACIÓN: Inicializar un conjunt buit, S.
- BÚSQUEDA: Per a cada forma xi en C:
- Calcular J(xi), el subconjunt de totes les formes en C que intersecan a xi (inclós el propi xi).
- Assignar N(xi) igual a les formes numèriques en J(xi).
- Elegir qualsevol xj tal que N(xj) siga un màxim, és dir, una forma que toque tantes formes com qualsevol atra.
- De totes les formes xi que intersecan a xj (inclosa la pròpia xj), seleccionar la forma x que toca la menor cantitat d'atres formes, és dir, un x tal que N(x) és un mínim.
- Agregar x a S.
- Eliminar x de C i eliminar J(x) i N(x).
- Si hi ha formes en C, retornar a BÚSQUEDA.
- FIN: tornar el conjunt S.
Per cada forma x que s'agrega a S, s'eliminen estes formes en N(x), perque estan intersecadas per x i, per lo tant, no es poden sumar a S més alvance. No obstant, algunes d'estes formes es creuen entre sí i, per lo tant, en qualsevol cas no és possible que totes estiguen en la solució òptima CDM(S). El subconjunt més gran de formes que "poden" estar en la solució òptima és "CDM(N(x))". Per lo tant, seleccionar una x que minimise |CDM(N(x))| minimisa la pèrdua en agregar x a S.
En particular, si es pot garantisar que existix una x per a la que |CDM(N(x))| està llimitada per una constant (pose's per cas, M), llavors este algoritme voraç produïx una aproximació constant del factor M, ya que es pot garantisar que:
Tal llímit superior M existix per a varis casos interessants:
Intervals unidimensionals: algoritme polinòmic exacte
Quan C és un conjunt d'intervals en una recta, M = 1 i, per lo tant, l'algoritme voraç troba el CDM exacte. Per a vore açò, suponga's sense pèrdua de generalitat que els intervals són verticals, i siga x l'interval en el punt final inferior més alt. Tots els demés intervals intersecados per x deuen creuar el seu punt final inferior. Per lo tant, tots els intervals en N(x) es creuen entre sí i CDM(N(x)) té un tamany de com a màxim 1 (vore la figura).
Per lo tant, en el cas unidimensional, el CDM es pot trobar exactament en el temps O(n log n):[2]
- Ordenar els intervals en orde ascendent dels seus punts finals inferiors (açò du temps O(n log n)).
- Agregar un interval en el punt final inferior més alt i eliminar tots els intervals que ho creuen.
- Continuar fins que no queden intervals.
Este algoritme és anàlec al de la solució de la data llímit més primerenca en primera programació en el problema de programació d'intervals.
En contrast en el cas unidimensional, en 2 o més dimensions el problema de trobar el CDM es torna NP-complet i, per lo tant, té algoritmes superpolinomiales exactes o algoritmes polinomiales aproximats.
Formes grosses: aproximacions de factor constant
Quan C és un conjunt de discs unitaris, M=3,[3] perque el disc més a l'esquerra (el disc el centre del qual té la coordenada x més menuda) interseca com a màxim atres 3 discs disjuntos (vore l'image). Per lo tant, l'algoritme voraç produïx una aproximació 3, és dir, troba un conjunt disjunto en un tamany d'a lo manco CDM(C)/3.
De manera similar, quan C és un conjunt de quadrats unitaris paralels als eixos, M=2.
Quan C és un conjunt de discs de tamany arbitrari, M=5, perque el disc en el radi més chicotet interseca com a màxim a atres 5 discs disjuntos (vore la figura).
De manera similar, quan C és un conjunt de quadrats paralels als eixos de tamany arbitrari, M = 4.
Es poden calcular atres constants per a uns atres polígons regulars.[3]
Algoritmes de dividix i venceràs
L'enfocament més comú per a trobar un CDM és el de dividix i venceràs. Un algoritme típic d'este enfocament s'assembla al següent:
- Dividir el conjunt de formes donat en dos o més subconjunts, de modo que les formes de cada subconjunt no puguen superpondre's a les formes d'atres subconjunts per consideracions geomètriques.
- Trobar recursivamente el CDM en cada subconjunt per separat.
- Tornar l'unió dels CDM de tots els subconjunts.
El principal desafiu d'este enfocament és trobar una forma geomètrica de dividir el conjunt en subconjunts. Açò pot requerir descartar una chicoteta cantitat de formes que no encaixen en cap dels subconjunts, com s'explica en les següents subsecciones.
Rectànguls paralels a l'eix en la mateixa altura: aproximació 2
Siga C un conjunt de n rectànguls paralels als eixos en el pla, tots en la mateixa altura H pero en llongituts variables. El següent algoritme troba un conjunt disjunto en un tamany d'a lo manco |CDM(C)|/2 en el temps O(n log n):[2]
- Dibuixar m llínees horisontals, tals que:
- La separació entre dos llínees és estrictament major que H.
- Cada llínea interseca a lo manco un rectàngul (per lo tant, m ≤ n).
- Cada rectàngul és intersecado per exactament una recta.
- Ya que l'altura de tots els rectànguls és H, no és possible que un rectàngul siga intersecado per més d'una recta. Per lo tant, les llínees rectes dividixen el conjunt de rectànguls en m subconjunts (): cada subconjunt inclou els rectànguls intersecados per una sola recta.
- Per a cada subconjunt , calcular un CDM exacte utilisant l'algoritme voraç unidimensional (vore dalt).
- Per construcció, els rectànguls en () solament poden intersecar rectànguls en o en . Per lo tant, cada una de les dos unions següents és un conjunt disjunto:
- Unió de CDM impar:
- Unió de CDM parells:
- Tornar la major d'estes dos unions. El seu tamany deu ser a lo manco |CDM|/2.
Rectànguls paralels a l'eix en la mateixa altura: EATP
Siga C un conjunt de n rectànguls paralels als eixos en el pla, tots en la mateixa altura pero en llongituts variables. Existix un algoritme que troba un conjunt disjunto en un tamany d'a lo manco |CDM(C)|/(1 + 1/k) en el temps O( n2k−1), per a cada constant k > 1.[2]
L'algoritme és una millora de l'aproximació 2 mencionada anteriorment, combinant programació dinàmica en la tècnica de desplaçament de Hochbaum i Maass.[4]
Este algoritme es pot generalisar a d dimensions. Si les etiquetes tenen el mateix tamany en totes les dimensions llevat una, és possible trobar una aproximació similar aplicant programació dinàmica en una de les dimensions. Açò també reduïx el temps a n^O(1/i).[5]
Rectànguls paralels a l'eix: aproximació de factor logarítmic
Siga C un conjunt de n rectànguls paralels als eixos en el pla. El següent algoritme troba un conjunt disjunto en un tamany d'a lo manco en el temps :[2]
- INICIALIZACIÓN: ordenar les vores horisontals dels rectànguls donats per la seua coordenada i, i les vores verticals per la seua coordenada x (este pas du temps O(n log n)).
- CONDICIÓN DE DETENCIÓN: si hi ha com a màxim n ≤ 2 formes, calcular el CDM directament i retornar.
- PARTE RECURSIVA:
- Siga la coordenada x mija.
- Dividir els rectànguls del problema en tres grups segons la seua relació en la recta : els que estan completament a la seua esquerra (), els que estan completament a la seua dreta () i els que intersecan en ella (). Per construcció, les cardinalidades de i són com a màxim n/2.
- Calcular recursivamente un CDM aproximat en () i en (), i calcular la seua unió. Per construcció, els rectànguls en i són tots disjuntos, per lo que és un conjunt disjunto.
- Calcular un CDM exacte en (). Ya que tots els rectànguls en intersecan una sola llínea recta vertical , este càlcul és equivalent a trobar un CDM a partir d'un conjunt d'intervals i es pot resoldre exactament en el temps O(n log n) (vore dalt).
- Torna o , el que siga major.
Es pot demostrar per inducció que, en l'últim pas, o tenen una cardinalidad d'a lo manco .
Chalermsookk i Chuzoy[6] varen millorar el factor a .
Chalermsookk i Walczak[7] varen presentar un algoritme d'aproximació a un entorn més general, en el que cada rectàngul té un "pes", i l'objectiu és trobar un conjunt independent de pes total màxim.
Rectànguls paralels a l'eix: aproximació de factor constant
Durant molt temps no es va saber si existix una aproximació de factor constant per a rectànguls paralels als seus eixos de diferents llongituts i altures. Es conjeturó que tal aproximació podria trobar-se utilisant "corts de guillotina". En particular, si existix un cort en guillotina de rectànguls paralels als eixos en els que els rectànguls estan separats, llavors es pot utilisar en un enfocament de programació dinàmica per a trobar una aproximació de factor constant al CDM.[8]<span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: sub.1.2
Fins a la data, no se sap si existix tal separació per mig de corts en guillotina. No obstant, existixen algoritmes d'aproximació de factor constant que utilisen corts pero sense guillotina:
- Joseph S. B. Mitchell va presentar un algoritme d'aproximació de 10 factors. El seu algoritme es basa en dividir el pla en "rectànguls retallats en els cantons".[9]
- Gálvez, Khan, Mari, Mömke, Pittu i Wiese varen presentar una part de l'algoritme basat en particionar el pla en una classe més general de polígons. Açò simplifica l'anàlisis i millora l'aproximació a 6 factors. Ademés, varen millorar l'aproximació al factor 3[10] i despuix al factor (2+ε).[11]
Objectes grossos d'idèntic tamany: EATP
Siga C un conjunt de n quadrats o círculs de tamany idèntic. Hochbaum i Maass[4] varen presentar un esquema d'aproximació de temps polinòmic per a trobar un CDM utilisant una estratègia simple de cuadrícula desplaçada. El procediment troba una solució dins de (1 − ε) del màxim en el temps nO(1/ε2), de temps i espai llineal. L'estratègia es generalisa a qualsevol colecció d'objecte gros d'aproximadament el mateix tamany (és dir, quan la relació de tamany màxim a mínim està llimitada per una constant).
Objectes grossos de qualsevol tamany: EATP
Siga C un conjunt de n objectes grossos, com a quadrats o círculs, de tamanys arbitraris. Existix un EATP per a trobar un CDM basat en l'alliniació de la cuadrícula en varis nivells. Ha segut descobert per dos grups aproximadament al mateix temps i descrit de dos maneres diferents.
Partició nivellada
Un algoritme de Erlebach, Jansen i Seidel[12] troba un conjunt disjunto en un tamany d'a lo manco (1 − 1/k)2 · |CDM(C)| en el temps nO(k2), per a cada constant k > 1. Funciona de la següent manera:
- Escalar els discs per a que el disc més chicotet tinga un diàmetro d'1. Dividir els discs en nivells, segons el logaritme del seu tamany. És dir, el nivell j conté tots els discs en diàmetro entre (k + 1)j i (k + 1)j+1, per a j ≤ 0 (el disc més chicotet està en el nivell 0).
- Per a cada nivell j, impondre una cuadrícula en el pla que consta de llínees que estan (k + 1)j+1 separades entre sí. Per construcció, cada disc pot creuar com a màxim una llínea horisontal i una llínea vertical des del seu nivell.
- Per a cada r, s entre 0 i k, definir D(r,s) com el subconjunt de discs que no són creuats per qualsevol llínea horisontal l'índex de la qual mòdul k siga r, ni per cap llínea vertical l'índex de la qual mòdul k siga s. Pel principi del colomer, existix a lo manco un parell (r,s) tal que , és dir, es pot trobar el CDM solament en D(r,s) i perdre solament una chicoteta fracció dels discs en la solució òptima:
- Per a tots els k2 valors possibles de r,s (0 ≤ r,s < k), calcular D(r,s) usant programació dinàmica.
- Torna el major d'estos conjunts k2.
Arbres cuádruples desplaçats
Un algoritme de Chan[5] troba un conjunt disjunto en un tamany d'a lo manco (1 − 2/k)·|CDM(C)| en el temps nO(k), per a cada constant k > 1.
L'algoritme utilisa arbres quadrats desplaçats. El concepte clau de l'algoritme és el de la "alliniació" en la cuadrícula de l'arbre cuádruple. Un objecte de tamany r es diu k-alineat (a on k ≥ 1 és una constant) si està dins d'una cela d'arbre cuádruple de tamany com a màxim kr(R ≤ kr).
Per definició, un objecte alineat en k que interseca el llímit d'una cela de quatre arbres de tamany R deu tindre un tamany d'a lo manco R/k (r > R/k). El llímit d'una cela de tamany R pot estar cobert per 4k quadrats de tamany R/k. Per lo tant, el número d'objectes grassos disjuntos que creuen el llímit d'eixa cela és com a màxim 4kc, a on c és una constant que medix la gruixa dels objectes.
Per lo tant, si tots els objectes són grossos i estan alineats en k, és possible trobar el conjunt disjunto màxim exacte en el temps nO(kc) usant un algoritme de dividix i venceràs. Comença en una cela de l'arbre cuádruple que continga tots els objectes. Després, es dividix de forma recursiva en celes de l'arbre cuádruple més menudes, es troba el màxim en cada cela més chicoteta i es combinen els resultats per a obtindre el màxim en la cela més gran. Ya que el número d'objectes grossos disjuntos que intersecan el llímit de cada cela de l'arbre cuádruple està llimitat per 4kc, es pot simplement "endevinar" quins objectes intersecan el llímit en la solució òptima i despuix aplicar dividix i venceràs als objectes en el seu interior.
Si casi tots els objectes estan alineats en k, es pot simplement descartar els objectes que no estan alineats en k i trobar un conjunt màxim disjunto dels objectes restants en el temps nO(k). Açò dona com resultat una aproximació (1 − i), a on i és la fracció d'objectes que no estan alineats en k.
Si la majoria dels objectes no estan alineats en k, es pot intentar alinear-los en k''desplaçant la cuadrícula en múltiples de (1/k,1/ k). Primer, escalar els objectes de modo que tots estiguen continguts en el quadrat unitari. Després, considerar els k desplaçaments de la cuadrícula: (0,0), (1/k,1/k), (2/k,2/ k), ..., ((k − 1)/k,(k − 1)/k' '). És dir, per a cada j en {0,...,k − 1}, considerar un desplaçament de la cuadrícula en (j/k,j/k). És possible demostrar que cada etiqueta estarà alineada en 2k per a a lo manco k −2 valors de j. Ara, per a cada j, descartar els objectes que no estiguen alineats en k en els bots de (j/k,j/k) i trobar el conjunt primari disjunto màxim dels objectes restants. Cridar a eixe conjunt A(j), i cridar al conjunt disjunto màxim real és A*. Llavors:
Per lo tant, el A(j) més gran té un tamany d'a lo manco: (1 − 2/k)|A*|. El valor de tornada de l'algoritme és el major A(j). El factor d'aproximació és (1 − 2/k) i el temps d'eixecució és nO(k). Es pot fer que el factor d'aproximació siga tan chicotet com es vullga, per lo que este és un EATP.
Abdós versions es poden generalisar a d dimensions (en diferents relacions d'aproximació) i al cas ponderat.
Algoritmes de separador geomètric
Varis algoritmes de dividix i venceràs es basen en la teorema del separador geomètric. Un separador geomètric és una llínea o forma que separa un conjunt determinat de formes en dos subconjunts més menuts, de modo que el número de formes perdudes durant la divisió és relativament menut. Açò permet tant treballar en procediments EATP i en algoritmes exactes subexponenciales, tal com s'explica a continuació.
Objectes grossos en tamanys arbitraris: EATP usant separadores geomètrics
Siga C un conjunt de nobjectes grossos, com a quadrats o círculs, de tamanys arbitraris. Chan[5] va descriure un algoritme que troba un conjunt disjunto en un tamany d'a lo manco (1 − O(Plantilla:Raïl))·|CDM(C)| en el temps nO(b), per a cada constant b > 1.
L'algoritme es basa en la següent teorema del separador geomètric, que es pot demostrar de manera similar a la prova de l'existència d'un separador geomètric per a quadrats disjuntos:
- Per a cada conjunt C d'objectes grossos, hi ha un rectàngul que dividix C en tres subconjunts d'objectes: Cinside, Coutside i Cboundary, tals que:
- |CDM(Cinside)| ≤ a|CDM(C)|
- |CDM(Coutside)| ≤ a|CDM(C)|
- |CDM(Cboundary)| cPlantilla:Raïl
- Per a cada conjunt C d'objectes grossos, hi ha un rectàngul que dividix C en tres subconjunts d'objectes: Cinside, Coutside i Cboundary, tals que:
a on a i c són constants. Si es poguera calcular CDM(C) exactament, seria possible fer que la constant a siga tan baixa com 2/3 per mig d'una selecció adequada del rectàngul separador. Pero com solament es pot aproximar el CDM(C) per mig d'un factor constant, la constant a deu ser major. Afortunadament, a seguix sent una constant independent de |C|.
Esta teorema del separador permet construir els següents EATP:
Seleccionar una constant b. Consultar totes les combinacions possibles de fins a b + 1 etiquetes.
- Si |CDM(C)| té un tamany de com a màxim b (és dir, tots els conjunts de b+1 etiquetes no estan separats), llavors simplement tornar eixe CDM i eixir. Este pas du un temps nO(b).
- De lo contrari, utilisar un separador geomètric per a separar C en dos subconjunts. Trobar el CDM aproximat en Cinside i Coutside per separat i tornar la seua combinació com el CDM aproximat en C.
Siga I(m) l'error de l'algoritme anterior quan el tamany òptim del CDM és CDM(C) = m. Quan m ≤ b, l'error és 0 perque el conjunt disjunto màxim es calcula exactament; quan m > b, l'error aumenta com a màxim cPlantilla:Raïl el número d'etiquetes intersecadas pel separador. El pijor cas per a l'algoritme és quan la divisió en cada pas està en la proporció màxima possible, que és a:(1 − a). Per tant, la funció d'error satisfà la següent relació de recurrencia:
La solució a esta recurrencia és:
és dir, . Es pot fer que el factor d'aproximació siga tan chicotet com es vullga per mig d'una selecció adequada de b.
Este EATP aforra més espai que el EATP basat en arbres cuádruples i pot manejar una generalisació en la que els objectes poden esgolar-se, pero no pot manejar el cas ponderat.
Discs en una relació de tamany acotada: algoritme subexponencial exacte
Siga C un conjunt de n discs, tal que la relació entre el radi major i el radi menor siga com a màxim r. El següent algoritme troba CDM(C) exactament en el temps .[13]
L'algoritme es basa en un separador geomètric acotat per ample en el conjunt Q dels centres de tots els discs en C. Esta teorema del separador permet construir el següent algoritme exacte:
- Trobar una llínea recta separadora tal que com a màxim 2n/3 centres estiguen a la seua dreta (Cright), com a màxim 2n/3 centres estiguen a la seua esquerra (C left), i com a màxim els O(Plantilla:Raïl) centres estan a una distància inferior a r/2 de la llínea recta (Cint).
- Considerar tots els possibles subconjunts no superposts de Cint. Hi ha com a màxim subconjunts d'este tipo. Per a cada u d'estos subconjunts, calcular recursivamente el CDM de Cleft i el CDM de Cright i tornar el conjunt combinat més gran.
El temps d'eixecució d'este algoritme satisfà la següent relació de recurrencia:
La solució a esta recurrencia és:
Algoritmes de busca local
Pseudodiscos: EATP
Un conjunt de pseudodiscos és un conjunt d'objectes en el que els llímits de cada parell d'objectes es creuen com a màxim dos voltes (tinga's en conte que esta definició es referix a una colecció completa i no diu res sobre les formes específiques dels objectes de la colecció). Un conjunt de pseudodiscos té una complexitat d'unió acotada, és dir, el número de punts d'intersecció en el llímit de l'unió de tots els objectes és llineal sobre el número d'objectes. Per eixemple, un conjunt de quadrats o círculs de tamanys arbitraris és un conjunt de pseudodiscos.
Siga C un conjunt de pseudodiscos en n objectes. Un algoritme de busca local de Chan i Har-Peled[14] permet trobar un conjunt disjunto de tamany a lo manco en el temps , per a cada constant sancera :
- INICIALIZACIÓN: inicializar un conjunt buit, .
- BÚSQUEDA: recórrer tots els subconjunts de el tamany dels quals estiga entre 1 i . Per a cada u d'eixos subconjunts X:
- Verificar que X siga independent (de lo contrari, passar al següent subconjunt).
- Calcular el conjunt I d'objectes en S que intersecan a X.
- Si és , eliminar I de S i insertar X: .
- FIN: tornar el conjunt S.
Cada intercanvi en el pas de busca aumenta el tamany de S en a lo manco 1 i, per lo tant, pot ocórrer com a màxim n voltes.
L'algoritme és molt simple, i la part difícil és demostrar la relació d'aproximació.[14]
Vore també al respecte el treball de P. K. Agarwal i de N. H. Mustafa.[15]
Algoritmes de relaixació en programació llineal
Pseudodiscos: EATP
Siga C un conjunt de pseudodiscos en n objectes i complexitat d'unió o. Usant relaixació en programació llineal, és possible trobar un conjunt disjunto de tamany a lo manco . Açò és possible en un algoritme aleatori que té una alta provabilitat d'èxit i un temps d'eixecució , o un algoritme determinista en un temps d'eixecució més llent (pero encara polinomial). Este algoritme es pot generalisar al cas ponderat.[14]
Referències
- ↑ Ravi, S. S.; Hunt, H. B.(1987).«An application of the planar separator theorem to counting problems».Information Processing Letters.25(5): 317.doi:10.1016/0020-0190(87)90206-7., Smith, W. D.; Wormald, N. C. (1998). «Geometric separator theorems and applications», Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pp. 232. doi:10.1109/sfcs.1998.743449. ISBN 978-0-8186-9172-0.
- ↑ 2,0 2,1 2,2 2,3 Agarwal, P. K.; Van Kreveld, M.; Suri, S.(1998).«Label placement by maximum independent set in rectangles».Computational Geometry.11(3–4): 209.doi:10.1016/s0925-7721(98)00028-5.
- ↑ 3,0 3,1 Marathe, M. V.; Breu, H.; Hunt, H. B.; Ravi, S. S.(1995).«Simple heuristics for unit disk graphs».Networks.25(2): 59.doi:10.1002/net.3230250205.
- ↑ 4,0 4,1 Hochbaum, D. S.; Maass, W.(1985).«Approximation schemes for covering and packing problems in image processing and VLSI».Journal of the ACM.32: 130–136.doi:10.1145/2455.214106.
- ↑ 5,0 5,1 5,2 Chan, T. M.(2003).«Polynomial-clave approximation schemes for packing and pírcing fat objects».Journal of Algorithms.46(2): 178–189.doi:10.1016/s0196-6774(02)00294-8.«citeseerx: 10.1.1.21.5344»
- ↑ Chalermsook, P.; Chuzhoy, J. (2009). «Maximum Independent Set of Rectangles», Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 892. doi:10.1137/1.9781611973068.97. ISBN 978-0-89871-680-1.
- ↑ Chalermsook, Parinya; Walczak, Bartosz(2021-01-01).«Coloring and Maximum Weight Independent Set of Rectangles».Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA).Society for Industrial and Applied Mathematics.: 860–868.doi:10.1137/1.9781611976465.54.Consultat el 2022-09-29.
- ↑ Abed, Fidaa; Chalermsook, Parinya; Correja, José; Karrenbauer, Andreas (2015). On Guillotine Cutting Sequences, pp. 1–19. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.1. ISBN 978-3-939897-89-7.
- ↑ arXiv:{{{arxiv}}}
- ↑ Gálvez, Waldo; Khan, Arindam; Mari, Mathieu; Mömke, Tobias(2022-01-01).«A 3-Approximation Algorithm for Maximum Independent Set of Rectangles».Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).Society for Industrial and Applied Mathematics.: 894–905.doi:10.1137/1.9781611977073.38.Consultat el 2022-09-29.
- ↑ arXiv:{{{arxiv}}}
- ↑ Erlebach, T.; Jansen, K.; Seidel, E.(2005).«Polynomial-Clave Approximation Schemes for Geometric Intersection Graphs».SIAM Journal on Computing.34(6): 1302.doi:10.1137/s0097539702402676.
- ↑ Fu, B.(2011).«Theory and application of width bounded geometric separators».Journal of Computer and System Sciences.77(2): 379–392.doi:10.1016/j.jcss.2010.05.003.
- ↑ 14,0 14,1 14,2 Chan, T. M.; Har-Peled, S.(2012).«Approximation Algorithms for Maximum Independent Set of Pseudo-Disks».Discrete & Computational Geometry.48(2): 373.doi:10.1007/s00454-012-9417-5.
- ↑ Agarwal, P. K.; Mustafa, N. H.(2006).«Independent set of intersection graphs of convex objects in 2D».Computational Geometry.34(2): 83.doi:10.1016/j.comgeo.2005.12.001.
Referències
- Este artícul conté una traducció derivada de «Conjunto disjunto máximo» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.