Número de intersección (teoría de grafos)

Menos camarillas que cubran los bordes de un gráfico

En el campo matemático de la teoría de grafos , el número de intersección de un grafo es el número más pequeño de elementos en una representación de como un grafo de intersección de conjuntos finitos . En tal representación, cada vértice se representa como un conjunto, y dos vértices están conectados por una arista siempre que sus conjuntos tengan un elemento común. De manera equivalente, el número de intersección es el número más pequeño de camarillas necesarias para cubrir todas las aristas de . ^{[1] [2]} ${\displaystyle G=(V,E)}$ ${\displaystyle G}$ ${\displaystyle G}$

Un conjunto de camarillas que cubren todas las aristas de un grafo se denomina cobertura de aristas de camarilla ^[3] o cobertura de camarilla de aristas [ ^4] o incluso simplemente cobertura de camarilla , aunque el último término es ambiguo: una cobertura de camarilla también puede ser un conjunto de camarillas que cubren todos los vértices de un grafo. ^[5] A veces se utiliza "cobertura" en lugar de "cobertura". ^[6] Además de llamarse número de intersección, el número mínimo de estas camarillas se ha denominado R - contenido ^[7] número de cobertura de camarilla de aristas ^[4] o número de cobertura de camarilla ^[8] El problema de calcular el número de intersección se ha denominado problema del número de intersección [ ^9] problema de la base del grafo de intersección ^[10] cobertura por camarillas [ ^10] problema de cobertura de camarilla de aristas [ 9 ^] y problema de conflicto de palabras clave ^[2 ]

Todo grafo con vértices y aristas tiene un número de intersección como máximo . El número de intersección es NP-difícil de calcular o aproximar, pero manejable con parámetros fijos . ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle \min(m,n^{2}/4)}$

Definiciones

Gráficas de intersección

Sea cualquier familia de conjuntos , permitiendo que los conjuntos en se repitan. Entonces el grafo de intersección de es un grafo no dirigido que tiene un vértice para cada conjunto en y una arista entre cada dos conjuntos que tienen una intersección no vacía. Todo grafo puede representarse como un grafo de intersección de esta manera. ^[11] El número de intersección del grafo es el número más pequeño tal que existe una representación de este tipo para la cual la unión de los conjuntos en tiene elementos. ^[1] El problema de encontrar una representación de intersección de un grafo con un número dado de elementos se conoce como el problema de la base del grafo de intersección . ^[10] ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle k}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle k}$

Cubiertas de borde de camarilla

Un gráfico con la intersección número cuatro. Las cuatro regiones sombreadas indican grupos que cubren todos los bordes del gráfico.

Una definición alternativa del número de intersección de un gráfico es que es el número más pequeño de camarillas en ( subgrafos completos de ) que juntos cubren todos los bordes de . ^{[1] [12]} Un conjunto de camarillas con esta propiedad se conoce como cobertura de borde de camarilla o cobertura de camarilla de borde , y por esta razón el número de intersección también se denomina a veces número de cobertura de camarilla de borde . ^[4] ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Equivalencia

La igualdad del número de intersección y el número de cobertura de la clique de aristas es sencilla de demostrar. En una dirección, supongamos que es el grafo de intersección de una familia de conjuntos cuya unión tiene elementos. Entonces, para cualquier elemento , el subconjunto de vértices de correspondiente a conjuntos que contienen forma una clique: dos vértices cualesquiera en este subconjunto son adyacentes, porque sus conjuntos tienen una intersección no vacía que contiene a . Además, cada arista en está contenida en una de estas cliques: si una arista proviene de una intersección no vacía de conjuntos que contienen un elemento , entonces esa arista está contenida en la clique para . Por lo tanto, las aristas de pueden ser cubiertas por cliques, una por elemento de . ^[12] ${\displaystyle G}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle U}$ ${\displaystyle k}$ ${\displaystyle x\in U}$ ${\displaystyle G}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle G}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle U}$

En la otra dirección, si un grafo puede ser cubierto por camarillas, entonces cada vértice de puede ser representado por un subconjunto de las camarillas, las que contienen al vértice . Dos de estos subconjuntos, para dos vértices y , tienen una intersección no vacía si y sólo si hay una camarilla en la intersección que los contiene a ambos, si y sólo si hay una arista incluida en una de las camarillas de recubrimiento. ^[12] ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle uv}$

Aplicaciones

La representación de un grafo como un grafo de intersección abstracto de conjuntos se puede utilizar para construir representaciones de intersección geométricas más concretas del mismo grafo. En particular, si un grafo tiene un número de intersección , se puede representar como un grafo de intersección de hiperesferas unitarias de dimensión n (su esfericidad es como máximo ). ^{[4] [13]} ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Una cubierta de clique se puede utilizar como una especie de esquema de etiquetado de adyacencia para un gráfico, en el que se etiqueta cada vértice con un valor binario con un bit para cada clique, cero si no pertenece al clique y uno si pertenece. Entonces dos vértices son adyacentes si y solo si el bit a bit y de sus etiquetas es distinto de cero. La longitud de las etiquetas es el número de intersección del gráfico. Este método se utilizó en una aplicación temprana de números de intersección, para etiquetar un conjunto de palabras clave de modo que las palabras clave en conflicto pudieran detectarse rápidamente, por E. Kellerman de IBM. Por esta razón, otro nombre para el problema de calcular números de intersección es el problema de conflicto de palabras clave . ^{[14] [15]} De manera similar, en geometría computacional , las representaciones basadas en el número de intersección se han considerado como una representación compacta para gráficos de visibilidad , pero existen entradas geométricas para las que esta representación requiere un número casi cuadrático de cliques. ^[16]

Otra clase de aplicaciones proviene de problemas de programación en los que varios usuarios de un recurso compartido deben programarse para intervalos de tiempo, de tal manera que las solicitudes incompatibles nunca se programen para el mismo intervalo de tiempo, sino que a todos los pares de solicitudes compatibles se les asigne al menos un intervalo de tiempo juntos. El número de intersección de un gráfico de compatibilidades proporciona el número mínimo de intervalos de tiempo necesarios para dicha programación. ^[2] En el diseño de compiladores para computadoras con palabras de instrucción muy largas , se puede utilizar una pequeña cobertura de camarilla de un gráfico de operaciones incompatibles para representar sus incompatibilidades mediante un pequeño número de recursos artificiales, lo que permite utilizar técnicas de programación basadas en recursos para asignar operaciones a intervalos de instrucciones. ^[17]

Shephard y Vetta observan que el número de intersecciones de cualquier red es igual al número mínimo de restricciones necesarias en una formulación de programación entera del problema de calcular conjuntos independientes máximos , en el que se tiene una variable 0-1 por vértice y una restricción de que en cada grupo de una cubierta de grupo las variables suman como máximo uno. Argumentan que, para los gráficos de intersección de caminos en ciertas redes de comunicaciones de fibra óptica , estos números de intersección son pequeños, lo que explica la relativa facilidad de resolver ciertos problemas de optimización en la asignación de ancho de banda en las redes. ^[3]

En estadística y visualización de datos , las cubiertas de camarillas de borde de un gráfico que representan pares de variables estadísticamente indistinguibles se utilizan para producir representaciones de letras compactas que ayudan a visualizar múltiples comparaciones por pares, asignando una letra u otro marcador visual para cada camarilla y usándolos para proporcionar una representación gráfica de qué variables son indistinguibles. ^{[18] [19]}

En el análisis de las redes alimentarias que describen las relaciones depredador-presa entre especies animales, un grafo de competencia o grafo de superposición de nicho es un grafo no dirigido en el que los vértices representan especies y los bordes representan pares de especies que compiten por la misma presa. Estos se pueden derivar de un grafo acíclico dirigido que representa las relaciones depredador-presa dibujando un borde en el grafo de competencia siempre que exista una especie de presa tal que el grafo de relación depredador-presa tenga bordes y . Cada grafo de competencia debe tener al menos un vértice aislado , y el número de competencia de un grafo arbitrario representa el número más pequeño de vértices aislados que podrían agregarse para convertirlo en un grafo de competencia. Biológicamente, si se observa parte de un grafo de competencia, entonces el número de competencia representa el número más pequeño posible de especies de presa no observadas necesarias para explicarlo. El número de competencia es como máximo igual al número de intersección: uno puede transformar cualquier grafo no dirigido en un grafo de competencia agregando una especie de presa para cada camarilla en una cubierta de camarilla de borde. Sin embargo, esta relación no es exacta, ya que también es posible que las especies depredadoras sean presas de otras especies. En un grafo con vértices, como máximo , pueden ser presas de más de una especie, por lo que el número de competencia es al menos el número de intersección menos . ^[20] ${\displaystyle u-v}$ ${\displaystyle w}$ ${\displaystyle u\to w}$ ${\displaystyle v\to w}$ ${\displaystyle n}$ ${\displaystyle n-2}$ ${\displaystyle n-2}$

Las cubiertas de clique de borde también se han utilizado para inferir la existencia de complejos proteicos , sistemas de proteínas que interactúan mutuamente, a partir de redes de interacción proteína-proteína que describen solo las interacciones por pares entre proteínas. ^[21] De manera más general, Guillaume y Latapy han argumentado que, para redes complejas de todo tipo, reemplazar la red por un gráfico bipartito que conecta sus vértices a los cliques en una cubierta de clique resalta la estructura en la red. ^[22]

Límites superiores

Trivialmente, un grafo con aristas tiene un número de intersección como máximo . Cada arista es en sí misma una camarilla de dos vértices. Hay de estas camarillas y juntas cubren todas las aristas. ^[23] También es cierto que cada grafo con vértices tiene un número de intersección como máximo . Más fuertemente, las aristas de cada grafo de -vértices pueden ser cubiertas por como máximo camarillas, todas las cuales son aristas simples o triángulos. Un algoritmo para encontrar esta cobertura es simple: eliminar dos vértices adyacentes y cubrir inductivamente el grafo restante. Restaurando los dos vértices eliminados, cubra las aristas de sus vecinos compartidos con triángulos, dejando las aristas de los vecinos no compartidos como camarillas de dos vértices. La cobertura inductiva tiene como máximo camarillas, y los dos vértices eliminados contribuyen como máximo a camarillas, maximizadas cuando todos los demás vértices son vecinos no compartidos y la arista entre los dos vértices debe usarse como camarilla. Sumando estas dos cantidades se obtiene el total de camarillas. ^{[2] [12]} Esto generaliza el teorema de Mantel de que un grafo sin triángulos tiene como máximo aristas, ya que en un grafo sin triángulos la única cobertura de aristas de camarilla óptima tiene una camarilla por arista y, por lo tanto, el número de intersecciones es igual al número de aristas. ^[2] ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle \lfloor n^{2}/4\rfloor }$ ${\displaystyle n}$ ${\displaystyle \lfloor n^{2}/4\rfloor }$ ${\displaystyle \lfloor (n-2)^{2}/4\rfloor }$ ${\displaystyle n-1}$ ${\displaystyle \lfloor n^{2}/4\rfloor }$ ${\displaystyle \lfloor n^{2}/4\rfloor }$

Un límite aún más estricto es posible cuando el número de aristas es estrictamente mayor que . Sea el número de pares de vértices que no están conectados por una arista en el grafo dado , y sea el entero único para el cual . Entonces el número de intersección de es como máximo . ^{[2] [24]} Los grafos que son el complemento de un grafo disperso tienen números de intersección pequeños: el número de intersección de cualquier grafo de -vértice es como máximo , donde es la base del logaritmo natural y es el grado máximo del grafo complementario de . ^[6] ${\displaystyle {\tfrac {n^{2}}{4}}}$ ${\displaystyle p}$ ${\displaystyle G}$ ${\displaystyle t}$ ${\displaystyle (t-1)t\leq p<t(t+1)}$ ${\displaystyle G}$ ${\displaystyle p+t}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle 2e^{2}(d+1)^{2}\ln n}$ ${\displaystyle e}$ ${\displaystyle d}$ ${\displaystyle G}$

De los resultados profundos sobre la estructura de los grafos sin garras se deduce que, cuando un grafo sin garras de vértice conexo tiene al menos tres vértices independientes, tiene un número de intersección como máximo . Sigue siendo un problema sin resolver si esto es cierto para todos los grafos sin garras sin requerir que tengan grandes conjuntos independientes. ^[8] Una subclase importante de los grafos sin garras son los grafos lineales , grafos que representan aristas y pares de aristas en contacto de algún otro grafo . Una cubierta de camarilla óptima del grafo lineal puede formarse con una camarilla para cada triángulo en que tenga dos o tres vértices de grado 2, y una camarilla para cada vértice que tenga un grado de al menos dos y no sea un vértice de grado dos de uno de estos triángulos. El número de intersección es el número de camarillas de estos dos tipos. ^[7] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle L(G)}$ ${\displaystyle G}$

En el modelo de Erdős–Rényi–Gilbert de grafos aleatorios , en el que todos los grafos en vértices etiquetados tienen la misma probabilidad (o equivalentemente, cada arista está presente o ausente, independientemente de otras aristas, con probabilidad ), el número de intersecciones de un grafo aleatorio de -vértices es con alta probabilidad menor por un factor de que el número de aristas. En estos grafos, las camarillas máximas tienen (con alta probabilidad) solo un número logarítmico de vértices, lo que implica que se necesitan esta cantidad de ellos para cubrir todas las aristas. La parte más complicada del límite es demostrar que es posible encontrar suficientes camarillas de tamaño logarítmico para cubrir muchas aristas, lo que permite que las aristas restantes queden cubiertas por camarillas de dos vértices. ^{[25] [26]} ${\displaystyle n}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle n}$ $${\displaystyle \Theta \left({\frac {n^{2}}{\log ^{2}n}}\right),}$$ ${\displaystyle \log ^{2}n}$

Gran parte de las primeras investigaciones sobre los números de intersección implicaban calcular estos números en varios gráficos específicos, como los gráficos formados al eliminar un subgráfico completo o una coincidencia perfecta de un gráfico completo más grande. ^[27]

Complejidad computacional

Probar si un gráfico dado tiene como máximo un número dado de intersección es NP-completo . ^{[10] [7] [15]} Por lo tanto, también es NP-difícil calcular el número de intersección de un gráfico dado. A su vez, la dificultad del número de intersección se ha utilizado para probar que es NP-completo reconocer los cuadrados de gráficos divididos . ^[28] ${\displaystyle G}$ ${\displaystyle k}$

El problema de calcular el número de intersección es, sin embargo, manejable con parámetros fijos : es decir, se puede resolver en una cantidad de tiempo limitada por un polinomio en multiplicado por una función más grande pero computable del número de intersección . ^{[5] [29]} Esto se puede demostrar observando que hay como máximo vecindarios cerrados distintos en el grafo – dos vértices que pertenecen al mismo conjunto de camarillas tienen el mismo vecindario – y que el grafo formado al seleccionar un vértice por vecindario cerrado tiene el mismo número de intersección que el grafo original. ^{[5] [30]} Por lo tanto, en tiempo polinomial la entrada se puede reducir a un núcleo más pequeño con como máximo vértices y aristas. La aplicación de un procedimiento de búsqueda de programación dinámica de tiempo exponencial sobre subconjuntos de aristas de este núcleo da tiempo , doble exponencial en . ^{[5] [29]} La dependencia doble exponencial de no se puede reducir a exponencial simple mediante una kernelización de tamaño polinomial, a menos que la jerarquía polinomial colapse, ^[31] y si la hipótesis del tiempo exponencial es verdadera, entonces la dependencia doble exponencial es necesaria independientemente de si se utiliza la kernelización. ^[29] En gráficos de ancho de árbol acotado , la programación dinámica en una descomposición en árbol del gráfico puede encontrar el número de intersección en tiempo lineal, ^{[32] [21]} pero los algoritmos más simples basados ​​en conjuntos finitos de reglas de reducción no funcionan. ^[32] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle 2^{k}}$ ${\textstyle 2^{k}}$ ${\displaystyle O(4^{k})}$ ${\displaystyle 2^{O(4^{k})}+n^{O(1)}}$ ${\displaystyle k}$ ${\displaystyle k}$

El problema no se puede aproximar en tiempo polinomial con una razón de aproximación mejor que , para alguna constante , ^[33] y se sabe que la mejor razón de aproximación es mejor que la trivial por solo un factor polilogarítmico. ^[5] Los investigadores en esta área también han investigado la eficiencia computacional de las heurísticas, sin garantías sobre la calidad de la solución que producen, y su comportamiento en redes del mundo real. ^{[5] [34]} ${\displaystyle n^{c}}$ ${\displaystyle c}$ ${\displaystyle O(n^{2})}$

Se conocen algoritmos más eficientes para ciertas clases especiales de grafos. El número de intersección de un grafo de intervalo siempre es igual a su número de camarillas máximas , que se puede calcular en tiempo polinomial. ^{[35] [36]} De manera más general, en grafos cordales , el número de intersección se puede calcular mediante un algoritmo que considera los vértices en un orden de eliminación del grafo (un orden en el que cada vértice y sus vecinos posteriores forman una camarilla) y que, para cada vértice , forma una camarilla para y sus vecinos posteriores siempre que al menos una de las aristas incidentes a no esté cubierta por ninguna camarilla anterior. ^[36] También es posible encontrar el número de intersección en tiempo lineal en grafos de arco circular . ^[37] Sin embargo, aunque estos grafos solo tienen un número polinomial de camarillas para elegir para la cobertura, tener pocas camarillas por sí solo no es suficiente para hacer que el problema sea fácil: existen familias de grafos con una cantidad polinomial de camarillas para las que el número de intersección sigue siendo NP-duro. ^[9] El número de intersección también se puede encontrar en tiempo polinomial para gráficos cuyo grado máximo es cinco, pero es NP-difícil para gráficos de grado máximo seis. ^{[38] [39]} En gráficos planares , calcular el número de intersección con exactitud sigue siendo NP-difícil, pero tiene un esquema de aproximación en tiempo polinomial basado en la técnica de Baker . ^[21] ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$

Véase también

• Dimensión bipartita , el menor número de biclínica necesarias para cubrir todos los bordes de un gráfico
• Gráfico acotado , un tipo de gráfico caracterizado por bordes de camarilla con una forma especial
• Cobertura de camarillas , el problema NP-difícil de encontrar una pequeña cantidad de camarillas que cubran todos los vértices de un gráfico

Referencias

1. Gross, Jonathan L.; Yellen, Jay (2006), Teoría de grafos y sus aplicaciones , CRC Press, pág. 440, ISBN 978-1-58488-505-4
2. Roberts, Fred S. (1985), "Aplicaciones de recubrimientos de aristas por camarillas", Discrete Applied Mathematics , 10 (1): 93–109, doi :10.1016/0166-218X(85)90061-7, MR  0770871
3. Shepherd, FB; Vetta, A. (noviembre de 2004), "Fibras de iluminación en una red oscura", IEEE Journal on Selected Areas in Communications , 22 (9): 1583–1588, doi :10.1109/jsac.2004.833850, S2CID  31868129
4. Michael, TS; Quint, Thomas (2006), "Esfericidad, cubicidad y coberturas de clique de aristas de grafos", Discrete Applied Mathematics , 154 (8): 1309–1313, doi :10.1016/j.dam.2006.01.004
5. Gramm, Jens; Guo, Jiong; Huffner, Falk; Niedermeier, Rolf (2009), "Reducción de datos y algoritmos exactos para la cobertura de camarillas" (PDF) , Journal of Experimental Algorithmics , 13 (2): 2–15, doi :10.1145/1412228.1412236, S2CID  15057639
6. Alon, Noga (1986), "Cobertura de gráficos por el número mínimo de relaciones de equivalencia" (PDF) , Combinatorica , 6 (3): 201–206, doi :10.1007/bf02579381, S2CID  13522339
7. Orlin, J. (1977), "Conformidad en la teoría de grafos: cubriendo grafos con camarillas", Indagationes Mathematicae , 80 (5): 406–424, doi :10.1016/1385-7258(77)90055-5
8. Javadi, Ramin; Hajebi, Sepehr (2019), "Cubierta de camarilla de borde de gráficos sin garras", Journal of Graph Theory , 90 (3): 311–405, arXiv : 1608.07723 , doi :10.1002/jgt.22403, MR  3904838, S2CID  67770018
9. Rosgen, Bill; Stewart, Lorna (2007), "Resultados de complejidad en gráficos con pocas camarillas", Matemáticas discretas y ciencias de la computación teórica , 9 (1): 127–135, doi : 10.46298/dmtcs.387 , MR  2335890
10. Garey, Michael R. ; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , Serie de libros sobre ciencias matemáticas (1.ª ed.), Nueva York: WH Freeman and Company , ISBN 9780716710455, MR  0519066, OCLC  247570676, Problemas GT17 (cobertura por camarillas) y GT59 (base del grafo de intersección)
11. Szpilrajn-Marczewski, Edward (1945), "Sur deux propriétés des Classes d'ensembles", Fundamenta Mathematicae (en francés), 33 : 303–307, doi : 10.4064/fm-33-1-303-307 , SEÑOR  0015448
12. Erdős, Paul ; Goodman, AW; Pósa, Louis (1966), "La representación de un gráfico mediante intersecciones establecidas" (PDF) , Canadian Journal of Mathematics , 18 (1): 106–112, CiteSeerX 10.1.1.210.6950 , doi :10.4153/CJM-1966- 014-3, SEÑOR  0186575, S2CID  646660 
13. Michael, TS; Quint, Thomas (2009), Erratum: Esfericidad, cubicidad y coberturas de clique de aristas de gráficos
14. Kellerman, E. (1973), "Determinación de conflictos de palabras clave", IBM Technical Disclosure Bulletin , 16 (2): 544–546, citado por Kou, Stockmeyer y Wong (1978)
15. Kou, LT; Stockmeyer, LJ ; Wong, CK (1978), "Cobertura de bordes por parte de camarillas con respecto a conflictos de palabras clave y gráficos de intersección", Communications of the ACM , 21 (2): 135–139, doi : 10.1145/359340.359346 , S2CID  15059696
16. Agarwal, PK ; Alon, N .; Aronov, B .; Suri, S. (1994), "¿Se pueden representar los gráficos de visibilidad de forma compacta?", Discrete & Computational Geometry , 12 (3): 347–365, doi : 10.1007/BF02574385 , MR  1298916
17. Rajagopalan, Subramanian; Vachharajani, Manish; Malik, Sharad (2000), "Manejo de ILP irregular dentro de programadores VLIW convencionales utilizando restricciones de recursos artificiales", Actas de la Conferencia internacional de 2000 sobre compiladores, arquitecturas y síntesis para sistemas integrados, CASES 2000, San José, California, EE. UU., 7 al 18 de noviembre de 2000 , Association for Computing Machinery, págs. 157–164, doi :10.1145/354880.354902, ISBN 1-58113-338-3, S2CID6498253 ​
18. Piepho, Hans-Peter (2004), "Un algoritmo para una representación basada en letras de comparaciones por pares", Journal of Computational and Graphical Statistics , 13 (2): 456–466, doi :10.1198/1061860043515, MR  2063995, S2CID  122068627
19. Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf; Piepho, Hans-Peter; Schmid, Ramona (2008), "Algoritmos para presentaciones de letras compactas: comparación y evaluación", Computational Statistics & Data Analysis , 52 (2): 725–736, doi :10.1016/j.csda.2006.09.035, MR  2418523
20. Opsut, Robert J. (1982), "Sobre el cálculo del número de competencia de un grafo", SIAM Journal on Algebraic and Discrete Methods , 3 (4): 420–428, doi :10.1137/0603043, MR  0679638
21. Blanchette, Mathieu; Kim, Ethan; Vetta, Adrian (2012), "Clique cover on sparse networks", en Bader, David A.; Mutzel, Petra (eds.), Actas de la 14.ª reunión sobre ingeniería de algoritmos y experimentos, ALENEX 2012, The Westin Miyako, Kioto, Japón, 16 de enero de 2012 , Society for Industrial and Applied Mathematics, págs. 93–102, doi :10.1137/1.9781611972924.10, ISBN 978-1-61197-212-2
22. Guillaume, Jean-Loup; Latapy, Matthieu (2004), "Estructura bipartita de todas las redes complejas" (PDF) , Information Processing Letters , 90 (5): 215–221, doi :10.1016/j.ipl.2004.03.007, MR  2054656, S2CID  6254096
23. Balakrishnan, VK (1997), Esquema de teoría y problemas de la teoría de grafos de Schaum , McGraw-Hill Professional, pág. 40, ISBN 978-0-07-005489-9
24. Lovász, L. (1968), "Sobre la cobertura de gráficos", en Erdős, P .; Katona, G. (eds.), Actas del coloquio celebrado en Tihany, Hungría, 1966 , Academic Press, págs.; como lo cita Roberts (1985)
25. Bollobás, Béla ; Erdős, Paul ; Spencer, Joel ; West, Douglas B. (1993), "Revestimientos de camarilla de los bordes de un gráfico aleatorio" (PDF) , Combinatorica , 13 (1): 1–5, doi :10.1007/BF01202786, MR  1221173, S2CID  26565829
26. Frieze, Alan ; Reed, Bruce (1995), "Cubrir los bordes de un gráfico aleatorio mediante camarillas", Combinatorica , 15 (4): 489–497, arXiv : 1103.4870 , doi :10.1007/BF01192522, MR  1364022, S2CID  7326662
27. Pullman, Norman J. (1983), "Recubrimientos de gráficos con clics: un estudio", en Reynolds, Louis; Casse, Antoine (eds.), Combinatorial Mathematics X: Proceedings of the Conference Held in Adelaide, Australia, August 23-27, 1982 , Lecture Notes in Mathematics, vol. 1036, Springer, págs. 72-85, doi :10.1007/bfb0071509, ISBN 978-3-540-12708-6, Sr.  0731572
28. Lau, Lap Chi; Corneil, Derek G. (2004), "Reconocimiento de potencias de grafos de intervalos propios, de división y cordales", SIAM Journal on Discrete Mathematics , 18 (1): 83–102, doi :10.1137/S0895480103425930, MR  2112490
29. Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2016), "Los algoritmos conocidos para la cobertura de clique de aristas son probablemente óptimos", SIAM Journal on Computing , 45 (1): 67–83, arXiv : 1203.1754 , doi :10.1137/130947076, MR  3448348, S2CID  11264145
30. Gyárfás, A. (1990), "Un límite inferior simple en recubrimientos de aristas por camarillas", Discrete Mathematics , 85 (1): 103–104, doi : 10.1016/0012-365X(90)90168-H , MR  1078317
31. Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michal; Wahlström, Magnus (2014), "Cobertura de camarillas y separación de grafos: nuevos resultados de incompresibilidad" (PDF) , ACM Transactions on Computation Theory , 6 (2): 6:1–6:19, doi :10.1145/2594439, S2CID  6887887
32. Bodlaender, Hans L. ; van Antwerpen-de Fluiter, Babette (2001), "Algoritmos de reducción para gráficos de ancho de árbol pequeño", Información y computación , 167 (2): 86–119, doi : 10.1006/inco.2000.2958 , MR  1835592
33. Lund, Carsten ; Yannakakis, Mihalis (1994), "Sobre la dificultad de aproximar problemas de minimización", Journal of the ACM , 41 (5): 960–981, doi : 10.1145/185675.306789 , MR  1371491
34. Conte, Alessio; Grossi, Roberto; Marino, Andrea (2020), "Cobertura de camarillas a gran escala de redes del mundo real", Información y computación , 270 , Artículo 104464, 15pp, doi :10.1016/j.ic.2019.104464, hdl : 11568/1028251 , MR  4050008, S2CID  203036455
35. Opsut, RJ; Roberts, FS (1981), "Sobre el mantenimiento de la flota, la frecuencia de radio móvil, la asignación de tareas y los problemas de sincronización del tráfico", en Chartrand, G .; Alavi, Y .; Goldsmith, DL; Lesniak-Foster, L.; Lick, DR (eds.), Actas de la 4.ª Conferencia internacional sobre la teoría y las aplicaciones de los grafos, Western Michigan University, Kalamazoo, Michigan, 6-9 de mayo de 1980 , Nueva York: Wiley, págs. 479-492, MR  0634549; como lo cita Roberts (1985)
36. Scheinerman, Edward R. ; Trenk, Ann N. (1999), "Sobre el número de intersección fraccionaria de un gráfico", Graphs and Combinatorics , 15 (3): 341–351, doi :10.1007/s003730050068, MR  1723018, S2CID  33081703
37. Hsu, Wen Lian; Tsai, Kuo-Hui (1991), "Algoritmos de tiempo lineal en gráficos de arco circular", Information Processing Letters , 40 (3): 123–129, doi :10.1016/0020-0190(91)90165-E, MR  1143909
38. Pullman, Norman J. (1984), "Cobertura de gráficos por clique, IV: Algoritmos", SIAM Journal on Computing , 13 (1): 57–75, doi :10.1137/0213005, MR  0731027
39. Hoover, DN (1992), "Complejidad de problemas de cobertura de grafos para grafos de bajo grado", Journal of Combinatorial Mathematics and Combinatorial Computing , 11 : 187–208, MR  1160076

Enlaces externos

• Weisstein, Eric W. , "Número de intersección", MathWorld