Oráculo matroide

Subrutina para probar la independencia

En matemáticas y ciencias de la computación, un oráculo matroide es una subrutina a través de la cual un algoritmo puede acceder a un matroide , una estructura combinatoria abstracta que puede usarse para describir las dependencias lineales entre vectores en un espacio vectorial o los árboles de expansión de un gráfico , entre otras aplicaciones.

El oráculo de este tipo más utilizado es el oráculo de independencia , una subrutina para comprobar si un conjunto de elementos matroides es independiente. También se han utilizado otros tipos de oráculos; se ha demostrado que algunos de ellos son más débiles que los oráculos de independencia, otros más fuertes y algunos equivalentes en potencia computacional. ^[1]

Muchos algoritmos que realizan cálculos sobre matroides han sido diseñados para tomar un oráculo como entrada, lo que les permite ejecutarse de manera eficiente sin cambios en muchos tipos diferentes de matroides y sin suposiciones adicionales sobre qué tipo de matroide están utilizando. Por ejemplo, dado un oráculo de independencia para cualquier matroide, es posible encontrar la base de peso mínima del matroide aplicando un algoritmo voraz que agrega elementos a la base en orden ordenado por peso, utilizando el oráculo de independencia para probar si se puede agregar cada elemento. ^[2]

En la teoría de la complejidad computacional , el modelo de oráculo ha llevado a límites inferiores incondicionales que prueban que ciertos problemas de matroides no se pueden resolver en tiempo polinomial, sin invocar suposiciones no probadas como la suposición de que P ≠ NP . Los problemas que han demostrado ser difíciles de esta manera incluyen probar si un matroide es binario o uniforme , o probar si contiene ciertos menores fijos . ^[3]

¿Por qué oráculos?

Aunque algunos autores han experimentado con representaciones informáticas de matroides que enumeran explícitamente todos los conjuntos independientes o todos los conjuntos base del matroide, ^[4] estas representaciones no son sucintas : un matroide con elementos puede expandirse en una representación que toma el espacio exponencialmente en . De hecho, el número de matroides distintos en elementos crece doblemente exponencialmente a medida que ${\displaystyle \scriptstyle n}$ ${\displaystyle \scriptstyle n}$ ${\displaystyle \scriptstyle n}$

${\displaystyle 2^{2^{n}n^{-3/2+o(1)}}}$^[5]

de lo cual se deduce que cualquier representación explícita capaz de manejar todos los matroides posibles utilizaría necesariamente el espacio exponencial. ^[6]

En cambio, se pueden representar de manera más eficiente diferentes tipos de matroides a partir de las otras estructuras a partir de las cuales se definen: matroides uniformes a partir de sus dos parámetros numéricos, matroides gráficas , matroides bicirculares y gamroides a partir de grafos, matroides lineales a partir de matrices , etc. Sin embargo, un algoritmo para realizar cálculos en matroides arbitrarias necesita un método uniforme para acceder a su argumento, en lugar de tener que rediseñarse para cada una de estas clases de matroides. El modelo de oráculo proporciona una forma conveniente de codificar y clasificar los tipos de acceso que un algoritmo podría necesitar.

Historia

A partir de Rado (1942), se han estudiado las "funciones de independencia" o "-funciones" como una de las muchas formas equivalentes de axiomatizar matroides. Una función de independencia asigna un conjunto de elementos de matroides al número si el conjunto es independiente o si es dependiente; es decir, es la función indicadora de la familia de conjuntos independientes, esencialmente lo mismo que un oráculo de independencia. ^[7] ${\displaystyle \scriptstyle I}$ ${\displaystyle \scriptstyle 1}$ ${\displaystyle \scriptstyle 0}$

Los oráculos de matroides también han formado parte de los primeros trabajos algorítmicos sobre matroides. Así, Edmonds (1965), al estudiar los problemas de partición de matroides, supuso que el acceso al matroide dado se hacía a través de una subrutina que toma como entrada un conjunto independiente y un elemento , y devuelve un circuito en (necesariamente único y que contiene , si existe) o determina que no existe tal circuito. Edmonds (1971) utilizó una subrutina que prueba si un conjunto dado es independiente (es decir, en terminología más moderna, un oráculo de independencia ), y observó que la información que proporciona es suficiente para encontrar la base de peso mínimo en tiempo polinomial. ${\displaystyle \scriptstyle I}$ ${\displaystyle \scriptstyle x}$ ${\displaystyle \scriptstyle I\cup \{x\}}$ ${\displaystyle \scriptstyle x}$

A partir del trabajo de Korte y Hausmann (1978) y Hausmann y Korte (1978), los investigadores comenzaron a estudiar los oráculos desde el punto de vista de la demostración de límites inferiores en algoritmos para matroides y estructuras relacionadas. Estos dos artículos de Hausmann y Korte se ocupaban del problema de encontrar un conjunto independiente de cardinalidad máxima, que es fácil para los matroides pero (como demostraron) más difícil de aproximar o calcular exactamente para sistemas de independencia más generales representados por un oráculo de independencia. Este trabajo dio inicio a una oleada de artículos a fines de la década de 1970 y principios de la de 1980 que mostraban resultados de dificultad similares para problemas en matroides ^[8] y comparaban la potencia de diferentes tipos de oráculos de matroides. ^[9]

Desde entonces, el oráculo de independencia se ha convertido en el estándar para la mayoría de las investigaciones sobre algoritmos matroides. ^[10] También ha habido investigaciones continuas sobre límites inferiores, ^[11] y comparaciones de diferentes tipos de oráculos. ^[12]

Tipos de oráculos

Se han considerado los siguientes tipos de oráculos matroides.

• Un oráculo de independencia toma como entrada un conjunto de elementos matroides y devuelve como salida un valor booleano , verdadero si el conjunto dado es independiente y falso en caso contrario. ^[13] Se puede implementar fácilmente en función de la estructura subyacente a partir de la cual se definió el matroide para matroides gráficos , matroides transversales , gamoides y matroides lineales, y para matroides formados a partir de estos mediante operaciones estándar como sumas directas. ^[3]
• Un oráculo base toma como entrada un conjunto de elementos matroides y devuelve como salida un valor booleano, verdadero si el conjunto dado es una base y falso en caso contrario. ^[9]
• Un oráculo de circuito toma como entrada un conjunto de elementos matroides y devuelve como salida un valor booleano, verdadero si el conjunto dado es un circuito y falso en caso contrario. ^[9]
• El oráculo de búsqueda de circuitos de Edmonds (1965) toma como entrada un conjunto independiente y un elemento adicional, y determina que su unión es independiente o encuentra un circuito en la unión y lo devuelve.
• Un oráculo de rango toma como entrada un conjunto de elementos matroides y devuelve como salida un valor numérico, el rango del conjunto dado. ^[9]
• Se han considerado tres tipos de oráculos de cierre : uno que prueba si un elemento dado pertenece al cierre de un conjunto dado, un segundo que devuelve el cierre del conjunto y un tercero que prueba si un conjunto dado está cerrado. ^[9]
• Un oráculo de expansión toma como entrada un conjunto de elementos matroides y devuelve como salida un valor booleano, verdadero si el conjunto dado es extenso (es decir, contiene una base y tiene el mismo rango que todo el matroide) y falso en caso contrario. ^[14]
• Un oráculo de circunferencia toma como entrada un conjunto de elementos matroides y devuelve como salida un valor numérico, el tamaño del circuito más pequeño dentro de ese conjunto (o si el conjunto dado es independiente). ^[14] ${\displaystyle \scriptstyle +\infty }$
• Un oráculo de puerto para un elemento fijo del matroide toma como entrada un conjunto de elementos del matroide y devuelve como salida un valor booleano, verdadero si el conjunto dado contiene un circuito que incluye y falso en caso contrario. ^[15] ${\displaystyle \scriptstyle x}$ ${\displaystyle \scriptstyle x}$

Poder relativo de diferentes oráculos

Aunque existen muchos tipos conocidos de oráculos, la elección de cuál utilizar se puede simplificar, porque muchos de ellos son equivalentes en potencia computacional. Se dice que un oráculo es polinomialmente reducible a otro oráculo si cualquier llamada a puede ser simulada por un algoritmo que accede al matroide utilizando solo oráculo y toma tiempo polinomial medido en términos del número de elementos del matroide; en términos de teoría de la complejidad, esta es una reducción de Turing . Se dice que dos oráculos son polinomialmente equivalentes si son polinomialmente reducibles entre sí. Si y son polinomialmente equivalentes, entonces cada resultado que prueba la existencia o inexistencia de un algoritmo de tiempo polinomial para un problema de matroide que utiliza oráculo también prueba lo mismo para oráculo . ${\displaystyle \scriptstyle X}$ ${\displaystyle \scriptstyle Y}$ ${\displaystyle \scriptstyle X}$ ${\displaystyle \scriptstyle Y}$ ${\displaystyle \scriptstyle X}$ ${\displaystyle \scriptstyle Y}$ ${\displaystyle \scriptstyle X}$ ${\displaystyle \scriptstyle Y}$

Por ejemplo, el oráculo de independencia es polinomialmente equivalente al oráculo de búsqueda de circuitos de Edmonds (1965). Si se dispone de un oráculo de búsqueda de circuitos, se puede probar la independencia de un conjunto utilizando como máximo llamadas al oráculo comenzando desde un conjunto vacío , añadiendo elementos del conjunto dado un elemento a la vez y utilizando el oráculo de búsqueda de circuitos para probar si cada adición preserva la independencia del conjunto que se ha construido hasta ahora. En la otra dirección, si se dispone de un oráculo de independencia, se puede encontrar el circuito en un conjunto utilizando como máximo llamadas al oráculo probando, para cada elemento , si es independiente y devolviendo los elementos para los que la respuesta es no. El oráculo de independencia también es polinomialmente equivalente al oráculo de rango, al oráculo de expansión, a los dos primeros tipos de oráculo de cierre y al oráculo de puerto. ^[1] ${\displaystyle \scriptstyle n}$ ${\displaystyle \scriptstyle I\cup \{x\}}$ ${\displaystyle \scriptstyle n}$ ${\displaystyle \scriptstyle y\in I}$ ${\displaystyle \scriptstyle I\setminus \{y\}\cup \{x\}}$

El oráculo de base, el oráculo de circuito y el oráculo que prueba si un conjunto dado está cerrado son todos más débiles que el oráculo de independencia: pueden ser simulados en tiempo polinomial por un algoritmo que accede al matroide usando un oráculo de independencia, pero no viceversa. Además, ninguno de estos tres oráculos puede simularse entre sí en tiempo polinomial. El oráculo de circunferencia es más fuerte que el oráculo de independencia, en el mismo sentido. ^[9]

Además de las reducciones de Turing en tiempo polinomial, también se han considerado otros tipos de reducibilidad. En particular, Karp, Upfal y Wigderson (1988) demostraron que, en algoritmos paralelos , los oráculos de rango e independencia son significativamente diferentes en potencia computacional. El oráculo de rango permite la construcción de una base de peso mínimo mediante consultas simultáneas de los prefijos del orden ordenado de los elementos del matroide: un elemento pertenece a la base óptima si y solo si el rango de su prefijo difiere del rango del prefijo anterior. Por el contrario, encontrar una base mínima con un oráculo de independencia es mucho más lento: se puede resolver de forma determinista en pasos de tiempo, y existe un límite inferior de par para algoritmos paralelos aleatorios. ${\displaystyle \scriptstyle n}$ ${\displaystyle \scriptstyle O({\sqrt {n}})}$ ${\displaystyle \scriptstyle \Omega ((n/\log n)^{1/3})}$

Algoritmos

Se sabe que muchos problemas sobre matroides pueden resolverse en tiempo polinómico mediante algoritmos que acceden al matroide únicamente a través de un oráculo de independencia u otro oráculo de potencia equivalente, sin necesidad de suposiciones adicionales sobre qué tipo de matroide se les ha asignado. Estos problemas que pueden resolverse polinómicamente incluyen:

• Encontrar una base de peso mínima o máxima de un matroide ponderado , utilizando un algoritmo voraz . ^[2]
• Partición de los elementos de un matroide en un número mínimo de conjuntos independientes y búsqueda del conjunto más grande que sea simultáneamente independiente en dos matroides dados. El último problema se denomina intersección de matroides y las soluciones de ambos problemas están estrechamente relacionadas entre sí. ^[16]
• Probar si un matroide está -conectado (en el sentido de Tutte 1966) para . ^[17] ${\displaystyle \scriptstyle k}$ ${\displaystyle \scriptstyle k\leq 3}$
• Probar si un matroide dado es gráfico ^[18] o regular . ^[19]
• Encontrar una descomposición en orejas de un matroide dado, una secuencia de circuitos cuya unión es el matroide y en la que cada circuito sigue siendo un circuito después de que todos los circuitos anteriores en la secuencia se contraen. Dicha descomposición también se puede encontrar con la propiedad adicional de que un elemento del matroide elegido pertenece a cada circuito. ^[15]
• Encontrar una descomposición en ramas de un matroide dado, siempre que su ancho de rama no sea mayor que una constante fija. ^[20]
• Enumeración de todas las bases, planos o circuitos de un matroide, en tiempo polinomial por conjunto de salida. ^[21]
• Aproximación del número de bases mediante un esquema de aproximación completamente aleatorio en tiempo polinomial , para un matroide con elementos y rango , con el supuesto adicional de que el número de bases está dentro de un factor polinomial del número de conjuntos de elementos. ^[22] ${\displaystyle \scriptstyle n}$ ${\displaystyle \scriptstyle r}$ ${\displaystyle \scriptstyle r}$

Pruebas de imposibilidad

Para muchos problemas de matroides, es posible demostrar que un oráculo de independencia no proporciona suficiente potencia para permitir que el problema se resuelva en tiempo polinomial. La idea principal de estas pruebas es encontrar dos matroides y en las que la respuesta al problema difiere y que son difíciles de distinguir para un algoritmo. En particular, si tiene un alto grado de simetría y difiere de solo en las respuestas a un pequeño número de consultas, entonces puede ser necesario un gran número de consultas para que un algoritmo esté seguro de distinguir una entrada de tipo de una entrada formada mediante el uso de una de las simetrías de para permutar . ^[3] ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle M'}$ ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle M'}$ ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle M'}$

Un ejemplo simple de este enfoque se puede utilizar para mostrar que es difícil probar si un matroide es uniforme . Para simplificar la exposición, sea par, sea el matroide uniforme , y sea un matroide formado a partir de haciendo que uno solo de los conjuntos base de elementos de sea dependiente en lugar de independiente. Para que un algoritmo pruebe correctamente si su entrada es uniforme, debe ser capaz de distinguir de cada permutación posible de . Pero para que un algoritmo determinista lo haga, debe probar cada uno de los subconjuntos de elementos de los elementos: si se olvida de un conjunto, podría ser engañado por un oráculo que eligiera ese mismo conjunto como el que se haría dependiente. Por lo tanto, probar si un matroide es uniforme puede requerir ${\displaystyle \scriptstyle n}$ ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle U{}_{n}^{n/2}}$ ${\displaystyle \scriptstyle M'}$ ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle n/2}$ ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle M'}$ ${\displaystyle \scriptstyle n/2}$

${\displaystyle {\binom {n}{n/2}}=\Omega \left({\frac {2^{n}}{\sqrt {n}}}\right)}$

consultas de independencia, mucho más altas que las polinómicas. Incluso un algoritmo aleatorio debe realizar casi tantas consultas para poder distinguir con seguridad estos dos matroides. ^[23]

Jensen y Korte (1982) formalizan este enfoque al demostrar que, siempre que existan dos matroides y en el mismo conjunto de elementos pero con diferentes respuestas al problema, un algoritmo que resuelva correctamente el problema dado en esos elementos debe utilizar al menos ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle M'}$

${\displaystyle {\frac {|\operatorname {aut} (M)|}{\sum _{i}|\operatorname {fix} (M,Q_{i})|}}}$

consultas, donde denota el grupo de automorfismos de , denota la familia de conjuntos cuya independencia difiere de a , y denota el subgrupo de automorfismos que se asigna a sí mismo. Por ejemplo, el grupo de automorfismos del matroide uniforme es simplemente el grupo simétrico , con tamaño , y en el problema de probar matroides uniformes solo había un conjunto con , más pequeño por un factor exponencial que . ^[24] ${\displaystyle \scriptstyle \operatorname {aut} (M)}$ ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle Q_{i}}$ ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle M'}$ ${\displaystyle \scriptstyle \operatorname {fix} (M,Q_{i})}$ ${\displaystyle \scriptstyle Q_{i}}$ ${\displaystyle \scriptstyle n!}$ ${\displaystyle \scriptstyle Q_{i}}$ ${\displaystyle \scriptstyle |\operatorname {fix} (M,Q_{i})|=(n/2)!^{2}}$ ${\displaystyle \scriptstyle n!}$

Los problemas que se ha demostrado que son imposibles de calcular para un algoritmo de oráculo matroide en tiempo polinomial incluyen:

• Comprobación de si un matroide dado es uniforme. ^[23]
• Probar si un matroide dado contiene un matroide fijo como menor, excepto en los casos especiales que es uniforme con rango o corank como máximo uno. De manera más general, si es un conjunto finito fijo de matroides, y no hay ningún matroide uniforme en , entonces no es posible probar en tiempo polinomial si un matroide dado contiene uno o más de los matroides en como menores. ^[25] ${\displaystyle \scriptstyle H}$ ${\displaystyle \scriptstyle H}$ ${\displaystyle \scriptstyle {\mathcal {H}}}$ ${\displaystyle \scriptstyle {\mathcal {H}}}$ ${\displaystyle \scriptstyle {\mathcal {H}}}$
• Probar si un matroide dado es binario , es representable sobre cualquier campo fijo particular o si existe un campo sobre el cual es representable. ^[26]
• Solución del problema de coincidencia de matroides, en el que la entrada es un gráfico y un matroide en sus vértices, y el objetivo es encontrar una coincidencia en el gráfico que sea lo más grande posible, sujeta a la restricción de que los vértices coincidentes formen un conjunto independiente. ^[27]
• Probar si un matroide dado es autodual , transversal , bipartito , euleriano u orientable . ^[3]
• Calcular la circunferencia (tamaño del circuito más pequeño), el tamaño del circuito más grande, el número de circuitos, el número de bases, el número de planos, el número de planos de rango máximo, el tamaño del plano más grande, el polinomio de Tutte o la conectividad de un matroide dado. ^[3]

Entre el conjunto de todas las propiedades de los matroides de elementos α, la fracción de las propiedades que no requieren tiempo exponencial para probarse tiende a cero, en el límite, ya que tiende a infinito. ^[6] ${\displaystyle \scriptstyle n}$ ${\displaystyle \scriptstyle n}$

Véase también

• Grupo de caja negra , un modelo tipo oráculo para la teoría de grupos
• Gráfico implícito , un modelo similar a un oráculo para algoritmos gráficos

Notas

1. Robinson y Welsh (1980); Hausmann y Korte (1981); Coullard y Hellerstein (1996).
2. Edmonds (1971).
3. Jensen y Korte (1982).
4. El hombre que se ha enamorado de mí" (2008).
5. Piff y galés (1971); Piff (1973); Knuth (1974); Bansal, Pendavingh y van der Pol (2012).
6. Robinson y Welsh (1980).
7. Para investigaciones adicionales sobre matroides basadas en la axiomatización de la función de independencia, véase, por ejemplo, Rado (1957), Lazarson (1958) e Ingleton (1959).
8. Lovász (1981); Seymour (1981); Seymour y Walton (1981); Jensen y Korte (1982); Truemper (1982).
9. Robinson y Welsh (1980); Hausmann y Korte (1981).
10. Véase, por ejemplo, Cunningham (1986), Kelmans y Polesskiĭ (1994), Fujishige y Zhang (1995), Chávez Lomelí y Welsh (1996), Khachiyan et al. (2005), y Oum y Seymour (2007).
11. Azar, Broder y Frieze (1994).
12. Karp, Upfal y Wigderson (1988); Coullard y Hellerstein (1996).
13. Edmonds (1971); Robinson y Gales (1980); Hausmann y Korte (1981).
14. Hausmann y Korte (1981).
15. Coullard y Hellerstein (1996).
16. Edmonds (1965); Cunningham (1986).
17. Bixby y Cunningham (1979). Cunningham y Edmonds anunciaron un artículo que afirmaba un resultado similar para cualquier constante fija aproximadamente al mismo tiempo, pero parece que no se publicó. Truemper (1998), págs. 186-187, escribe: "Localizar sumas para general es mucho más difícil... No sabemos cómo se puede lograr esto de manera eficiente para matroides binarios, y mucho menos para matroides generales". ${\displaystyle \scriptstyle k}$ ${\displaystyle \scriptstyle k}$ ${\displaystyle \scriptstyle k\geq 4}$
18. Seymour (1981).
19. Truemper (1982).
20. Oum y Seymour (2007).
21. Khachiyan y otros (2005).
22. Chávez Lomelí & Welsh (1996). Por el contrario, no es posible que los algoritmos deterministas aproximen con precisión el número de bases de un matroide en tiempo polinomial (Azar, Broder & Frieze 1994).
23. Robinson y Welsh (1980); Jensen y Korte (1982).
24. Además de encontrarse en Jensen y Korte (1982), esta formalización se analiza en Korte y Schrader (1981). En la mayoría de las aplicaciones de esta técnica en Jensen y Korte (1982), es uniforme, pero Seymour (1981) aplica la misma idea a un matroide no uniforme pero altamente simétrico. ${\displaystyle \scriptstyle M}$
25. Seymour y Walton (1981). Los resultados de Seymour (1981) y Jensen y Korte (1982) dan casos especiales de esto para los problemas de encontrar un menor y un menor matroide de Vámos , respectivamente. La comprobación de si un matroide es gráfico o regular se puede expresar en términos de un conjunto finito de menores prohibidos, y se puede resolver en tiempo polinomial, pero los menores prohibidos para estos problemas incluyen el matroide uniforme , por lo que no contradicen este resultado de imposibilidad. ${\displaystyle \scriptstyle U{}_{4}^{2}}$ ${\displaystyle \scriptstyle U{}_{4}^{2}}$
26. Seymour (1981) demostró esto para matroides binarios, Seymour y Walton (1981) para campos finitos, Truemper (1982) para campos arbitrarios y Jensen y Korte (1982) para la existencia de un campo sobre el cual el matroide es representable.
27. Lovász (1981); Jensen y Korte (1982). Sin embargo, el caso especial de este problema para grafos bipartitos se puede resolver en tiempo polinomial como un problema de intersección de matroides .

Referencias

• Azar, Y.; Broder, AZ ; Frieze, AM (1994), "Sobre el problema de aproximar el número de bases de un matroide", Information Processing Letters , 50 (1): 9–11, doi :10.1016/0020-0190(94)90037-X, MR  1279491.
• Bansal, N.; Pendavingh, R.; van der Pol, J. (2012), Sobre el número de matroides , arXiv : 1206.6270 , Bibcode : 2012arXiv1206.6270B.
• Bixby, Robert E.; Cunningham, William H. (1979), "Matroides, grafos y conectividad tridimensional", Teoría de grafos y temas relacionados (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977) , Nueva York: Academic Press, págs. 91-103, MR  0538038.
• Chávez Lomelí, Laura; Welsh, Dominic (1996), "Aproximación aleatoria del número de bases", Matroid Theory (Seattle, WA, 1995) , Contemporary Mathematics, vol. 197, Providence, RI: American Mathematical Society, pp. 371–376, doi :10.1090/conm/197/02534, ISBN 978-0-8218-0508-4, Sr.  1411698.
• Coullard, Collette R. ; Hellerstein, Lisa (1996), "Independencia y oráculos de puerto para matroides, con una aplicación a la teoría del aprendizaje computacional", Combinatorica , 16 (2): 189–208, doi :10.1007/BF01844845, MR  1401892.
• Cunningham, William H. (1986), "Límites mejorados para algoritmos de partición e intersección de matroides", SIAM Journal on Computing , 15 (4): 948–957, doi :10.1137/0215066, MR  0861361.
• Edmonds, Jack (1965), "Partición mínima de un matroide en subconjuntos independientes", Journal of Research of the National Bureau of Standards , 69B : 67–72, doi : 10.6028/jres.069b.004 , MR  0190025.
• Edmonds, Jack (1971), "Matroides y el algoritmo voraz", Programación matemática , 1 : 127–136, doi :10.1007/BF01584082, MR  0297357.
• Fujishige, Satoru; Zhang, Xiaodong (1995), "Un algoritmo de escalamiento de costos eficiente para el problema de asignación independiente", Journal of the Operations Research Society of Japan , 38 (1): 124–136, doi :10.15807/jorsj.38.124, MR  1337446.
• Hausmann, Dirk; Korte, Bernhard (1978), "Límites inferiores de la complejidad del peor caso de algunos algoritmos de oráculo", Discrete Mathematics , 24 (3): 261–276, doi : 10.1016/0012-365X(78)90097-3 , MR  0523316.
• Hausmann, D.; Korte, B. (1981), "Definiciones algorítmicas versus axiomáticas de matroides", Programación matemática en Oberwolfach (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979) , Estudios de programación matemática, vol. 14, págs. 98-111, doi :10.1007/BFb0120924, ISBN 978-3-642-00805-4, Sr.  0600125.
• Ingleton, AW (1959), "Una nota sobre funciones de independencia y rango", Journal of the London Mathematical Society , Segunda serie, 34 : 49–56, doi :10.1112/jlms/s1-34.1.49, MR  0101848.
• Jensen, Per M.; Korte, Bernhard (1982), "Complejidad de los algoritmos de propiedades de matroides", SIAM Journal on Computing , 11 (1): 184–190, doi :10.1137/0211014, MR  0646772.
• Karp, Richard M. ; Upfal, Eli ; Wigderson, Avi (1988), "La complejidad de la búsqueda paralela", Journal of Computer and System Sciences , 36 (2): 225–253, doi :10.1016/0022-0000(88)90027-X, MR  0950432.
• Kelmans, AK; Polesskiĭ, VP (1994), "Conjuntos extremos y problemas de cubrimiento y empaquetamiento en matroides", Selected topics in discrete mathematics (Moscú, 1972–1990) , Amer. Math. Soc. Transl. Ser. 2, vol. 158, Providence, RI: Amer. Math. Soc., págs. 149–174, MR  1269136.
• Khachiyan, L. ; Boros, E. ; Elbassioni, K. ; Gurvich, V. ; Makino, K. (2005), "Sobre la complejidad de algunos problemas de enumeración para matroides", SIAM Journal on Discrete Mathematics , 19 (4): 966–984, CiteSeerX  10.1.1.124.4286 , doi :10.1137/S0895480103428338, MR  2206374.
• Knuth, Donald E. (1974), "El número asintótico de las geometrías", Journal of Combinatorial Theory , Serie A, 16 (3): 398–400, doi : 10.1016/0097-3165(74)90063-6 , MR  0335312.
• Korte, Bernhard; Hausmann, Dirk (1978), "Un análisis de la heurística voraz para sistemas independientes", Aspectos algorítmicos de la combinatoria (Conf., Isla de Vancouver, BC, 1976) , Annals of Discrete Mathematics, vol. 2, págs. 65–74, doi :10.1016/S0167-5060(08)70322-4, ISBN 978-0-7204-1043-3, Sr.  0500689.
• Korte, B.; Schrader, R. (1981), "A survey on oracle technique", en Gruska, Jozef; Chytil, Michal (eds.), Mathematical Foundations of Computer Science 1981, Actas, 10.º Simposio Štrbské Pleso, Checoslovaquia, 31 de agosto – 4 de septiembre de 1981 , Lecture Notes in Computer Science, vol. 118, Berlín: Springer, págs. 61–77, doi :10.1007/3-540-10856-4_74, ISBN 978-3-540-10856-6, Sr.  0652740.
• Lazarson, T. (1958), "El problema de representación para funciones independientes", Journal of the London Mathematical Society , Segunda serie, 33 : 21–25, doi :10.1112/jlms/s1-33.1.21, MR  0098701.
• Lovász, L. (1981), "El problema de coincidencia de matroides", Métodos algebraicos en teoría de grafos, vol. I, II (Szeged, 1978) , Coloq. Matemáticas. Soc. János Bolyai, vol. 25, Ámsterdam: Holanda Septentrional, págs. 495–517, SEÑOR  0642059.
• Mayhew, Dillon (2008), "Complejidad de matroides y descripciones no sucintas", SIAM Journal on Discrete Mathematics , 22 (2): 455–466, arXiv : math/0702567 , doi :10.1137/050640576, MR  2399359.
• Oum, Sang-il ; Seymour, Paul (2007), "Prueba del ancho de rama", Journal of Combinatorial Theory , Serie B, 97 (3): 385–393, doi : 10.1016/j.jctb.2006.06.006 , MR  2305892.
• Piff, MJ (1973), "Un límite superior para el número de matroides", Journal of Combinatorial Theory , Serie B, 14 (3): 241–245, doi :10.1016/0095-8956(73)90006-3, MR  0316282.
• Piff, MJ; Welsh, DJA (1971), "El número de geometrías combinatorias", The Bulletin of the London Mathematical Society , 3 : 55–56, doi :10.1112/blms/3.1.55, MR  0282867.
• Rado, R. (1942), "Un teorema sobre relaciones de independencia", The Quarterly Journal of Mathematics , Segunda serie, 13 : 83–89, Bibcode :1942QJMat..13...83R, doi :10.1093/qmath/os-13.1.83, MR  0008250.
• Rado, R. (1957), "Nota sobre funciones de independencia", Actas de la London Mathematical Society , Tercera serie, 7 : 300–320, doi :10.1112/plms/s3-7.1.300, MR  0088459.
• Robinson, GC; Welsh, DJA (1980), "La complejidad computacional de las propiedades de los matroides", Mathematical Proceedings of the Cambridge Philosophical Society , 87 (1): 29–45, Bibcode :1980MPCPS..87...29R, doi :10.1017/S0305004100056498, MR  0549295.
• Seymour, PD (1981), "Reconocimiento de matroides gráficos", Combinatorica , 1 (1): 75–78, doi :10.1007/BF02579179, MR  0602418.
• Seymour, PD ; Walton, PN (1981), "Detección de menores matroides", Journal of the London Mathematical Society , Segunda serie, 23 (2): 193–203, doi :10.1112/jlms/s2-23.2.193, MR  0609098.
• Truemper, K. (1982), "Sobre la eficiencia de las pruebas de representabilidad para matroides", European Journal of Combinatorics , 3 (3): 275–291, doi :10.1016/s0195-6698(82)80039-5, MR  0679212.
• Truemper, K. (1998), Descomposición matroide (PDF) (edición revisada).
• Tutte, WT (1966), "Conectividad en matroides", Revista canadiense de matemáticas , 18 : 1301–1324, doi : 10.4153/CJM-1966-129-2 , MR  0205880.