oráculo matroide

Subrutina para probar la independencia.

En matemáticas e informática, un oráculo matroide es una subrutina a través de la cual un algoritmo puede acceder a una 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 otros. aplicaciones.

El oráculo de este tipo más comúnmente utilizado es un oráculo de independencia , una subrutina para probar 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 otros equivalentes en poder computacional. ^[1]

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

En la teoría de la complejidad computacional , el modelo de Oracle ha llevado a límites inferiores incondicionales que demuestran que ciertos problemas matroides no se pueden resolver en tiempo polinomial, sin invocar suposiciones no probadas como la suposición de que P ≠ NP . Los problemas que se ha demostrado que son difíciles de esta manera incluyen probar si una matroide es binaria 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 de bases de la matroide, ^[4] estas representaciones no son sucintas : una matroide con elementos puede expandirse hasta convertirse en una representación que ocupa un espacio exponencial en . De hecho, el número de matroides distintas en los 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 todas las matroides posibles necesariamente utilizaría el espacio exponencial. ^[6]

En cambio, diferentes tipos de matroides pueden representarse más eficientemente a partir de 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 gammaides a partir de gráficos, matroides lineales a partir de matrices , etc. Un algoritmo para realizar cálculos en matroides arbitrarias necesita un método uniforme para acceder a su argumento, en lugar de tener que ser rediseñado para cada una de estas clases de matroides. El modelo de Oracle proporciona una manera conveniente de codificar y clasificar los tipos de acceso que podría necesitar un algoritmo.

Historia

A partir de Rado (1942), las "funciones de independencia" o " funciones -" se han estudiado como una de las muchas formas equivalentes de axiomatizar las matroides. Una función de independencia asigna un conjunto de elementos matroides al número si el conjunto es independiente o 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 matroides también han sido parte de los primeros trabajos algorítmicos sobre matroides. Así, Edmonds (1965), al estudiar problemas de partición de matroides, supuso que el acceso a la matroide dada se realizaba 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 & Hausmann (1978) y Hausmann & Korte (1978), los investigadores comenzaron a estudiar los oráculos desde el punto de vista de demostrar límites inferiores en algoritmos para matroides y estructuras relacionadas. Estos dos artículos de Hausmann y Korte se referían al problema de encontrar un conjunto independiente de cardinalidad máxima, que es fácil para las 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 inició una avalancha de artículos a finales de los años 1970 y principios de los 1980 que mostraban resultados de dureza similares para problemas en matroides ^[8] y comparaban el poder de diferentes tipos de oráculos matroides. ^[9]

Desde entonces, el oráculo de la 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áculo. ^[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] Puede implementarse fácilmente basándose en la estructura subyacente a partir de la cual se definió la matroide para matroides gráficas , matroides transversales , gammoides y matroides lineales, y para matroides formadas a partir de estas 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áculo 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 de expansión (es decir, contiene una base y tiene el mismo rango que toda la matroide) y falso en caso contrario. ^[14]
• Un oráculo circunferencial 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 de la matroide toma como entrada un conjunto de elementos de 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 puede simplificarse, porque muchos de ellos son equivalentes en potencia computacional. Se dice que un oráculo es polinómicamente reducible a otro oráculo si cualquier llamada a puede ser simulada mediante un algoritmo que accede a la matroide utilizando únicamente el oráculo y toma el tiempo polinómico medido en términos del número de elementos de la matroide; en términos de teoría de la complejidad, esto es una reducción de Turing . Se dice que dos oráculos son polinómicamente equivalentes si son polinomialmente reducibles entre sí. Si y son polinomialmente equivalentes, entonces cada resultado que prueba la existencia o no existencia de un algoritmo de tiempo polinomial para un problema matroide usando Oracle también prueba lo mismo para Oracle . ${\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 la independencia es polinómicamente 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 usando como máximo llamadas al oráculo comenzando desde un conjunto vacío , agregando elementos del conjunto dado un elemento a la vez y usando el oráculo de búsqueda de circuitos para Probar si cada suma preserva la independencia del conjunto que se ha construido hasta el momento. En la otra dirección, si hay disponible un oráculo de independencia, el circuito en un conjunto se puede encontrar usando como máximo llamadas al oráculo probando, para cada elemento , si es independiente y devolviendo los elementos para los cuales la respuesta es no. El oráculo de la 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 base, el oráculo del circuito y el oráculo que prueba si un conjunto dado es cerrado son todos más débiles que el oráculo de la independencia: pueden simularse en tiempo polinomial mediante un algoritmo que accede a la matroide utilizando un oráculo de la independencia, pero no al revés. . Además, ninguno de estos tres oráculos puede simularse entre sí en un tiempo polinómico. El oráculo de la circunferencia es más fuerte que el oráculo de la 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 poder 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 de los elementos matroides: un elemento pertenece a la base óptima si y sólo si el rango de su prefijo difiere del rango del anterior prefijo. Por el contrario, encontrar una base mínima con un oráculo de independencia es mucho más lento: se puede resolver de manera 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 de matroides se pueden resolver en tiempo polinomial , mediante algoritmos que acceden a la matroide sólo a través de un oráculo de independencia u otro oráculo de poder equivalente, sin necesidad de suposiciones adicionales sobre qué tipo de matroide se les ha dado. Estos problemas con solución polinomial incluyen:

• Encontrar una base de peso mínimo o máximo de una matroide ponderada , utilizando un algoritmo codicioso . ^[2]
• Dividir los elementos de una matroide en un número mínimo de conjuntos independientes y encontrar el conjunto más grande que sea simultáneamente independiente en dos matroides dadas. El último problema se llama intersección matroide y las soluciones a ambos problemas están estrechamente relacionadas entre sí. ^[dieciséis]
• Probar si una matroide está conectada (en el sentido de Tutte 1966) para . ^[17] ${\displaystyle \scriptstyle k}$ ${\displaystyle \scriptstyle k\leq 3}$
• Probar si una matroide determinada es gráfica ^[18] o regular . ^[19]
• Encontrar una descomposición del oído de una matroide determinada, una secuencia de circuitos cuya unión es la matroide y en la que cada circuito sigue siendo un circuito después de que todos los circuitos anteriores de la secuencia se contraen. Esta descomposición también se puede encontrar con la propiedad adicional de que un elemento matroide elegido pertenece a cada circuito. ^[15]
• Encontrar una descomposición de rama de una matroide determinada, siempre que su ancho de rama no sea más que una constante fija. ^[20]
• Enumerar todas las bases, planos o circuitos de una matroide, en tiempo polinómico por conjunto de salida. ^[21]
• Aproximar el número de bases mediante un esquema de aproximación aleatorio en tiempo totalmente polinomial , para una 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 matroides, es posible demostrar que un oráculo de independencia no proporciona suficiente poder para permitir que el problema se resuelva en tiempo polinomial. La idea principal de estas pruebas es encontrar dos matroides en las que la respuesta al problema difiere y que son difíciles de diferenciar para un algoritmo. En particular, si tiene un alto grado de simetría y difiere sólo 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. formado usando una de las simetrías de permutar . ^[3] ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle M'}$ ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle M'}$ ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle M}$ ${\displaystyle \scriptstyle M'}$

Se puede utilizar un ejemplo sencillo de este enfoque para demostrar que es difícil comprobar si una matroide es uniforme . Para simplificar la exposición, sea par, sea la matroide uniforme y sea una matroide formada al hacer uno solo de los conjuntos de bases de elementos dependientes en lugar de independientes. Para que un algoritmo pruebe correctamente si su entrada es uniforme, debe poder distinguir entre todas las permutaciones posibles de . Pero para que un algoritmo determinista lo haga, debe probar cada uno de los subconjuntos de elementos: si omitió un conjunto, podría ser engañado por un oráculo que eligiera ese mismo conjunto como el que convertiría en dependiente. Por lo tanto, probar si una 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 polinomiales. Incluso un algoritmo aleatorio debe realizar casi tantas consultas para poder distinguir con seguridad estas dos matroides. ^[23]

Jensen y Korte (1982) formalizan este enfoque demostrando 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 automorfismo de la matroide uniforme es solo 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 en 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 en tiempo polinómico para un algoritmo de Oracle matroide incluyen:

• Probar si una matroide determinada es uniforme. ^[23]
• Probar si una matroide determinada contiene una matroide fija como menor, excepto en casos especiales que sea 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 una matroide uniforme en , entonces no es posible probar en tiempo polinómico si una matroide determinada contiene una o más matroides en como menor. ^[25] ${\displaystyle \scriptstyle H}$ ${\displaystyle \scriptstyle H}$ ${\displaystyle \scriptstyle {\mathcal {H}}}$ ${\displaystyle \scriptstyle {\mathcal {H}}}$ ${\displaystyle \scriptstyle {\mathcal {H}}}$
• Probar si una matroide determinada es binaria , es representable sobre cualquier campo fijo particular , o si existe un campo sobre el cual sea representable. ^[26]
• Resolver el problema de coincidencia de matroides, en el que la entrada es un gráfico y una matroide en sus vértices, y el objetivo es encontrar una coincidencia en el gráfico que sea lo más grande posible, sujeto a la restricción de que los vértices coincidentes formen un conjunto independiente . ^[27]
• Probar si una matroide determinada es autodual , transversal , bipartita , euleriana o orientable . ^[3]
• Calcular la circunferencia (tamaño del circuito más pequeño), tamaño del circuito más grande, número de circuitos, número de bases, número de pisos, número de pisos de rango máximo, tamaño del piso más grande, polinomio de Tutte o conectividad de un determinado matroide. ^[3]

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

Ver 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 de 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. Mayhew (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, consulte, 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 galés (1980); Hausmann y Korte (1981).
10. Véase, por ejemplo, Cunningham (1986), Kelmans & Polesskiĭ (1994) Fujishige & Zhang (1995), Chávez Lomelí & 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 no haber sido publicado. Truemper (1998), págs. 186-187, escribe: "Localizar sumas -para generales es mucho más difícil... No sabemos cómo se puede lograr esto de manera eficiente para matroides binarias, 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í & Galés (1996). Por el contrario, los algoritmos deterministas no pueden aproximar con precisión el número de bases de una matroide en tiempo polinómico (Azar, Broder y 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 una matroide no uniforme pero altamente simétrica. ${\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 Vámos matroide menor, respectivamente. Probar si una matroide es gráfica o regular puede expresarse en términos de un conjunto finito de menores prohibidos y puede resolverse en tiempo polinomial, pero los menores prohibidos para estos problemas incluyen la 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 binarias, 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 la matroide es representable.
27. Lovász (1981); Jensen y Korte (1982). Sin embargo, el caso especial de este problema para gráficos bipartitos se puede resolver en tiempo polinomial como un problema de intersección matroide .

Referencias

• Azar, Y.; Broder, Arizona ; Frieze, AM (1994), "Sobre el problema de aproximar el número de bases de una 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, gráficos y 3-conectividad", Teoría de grafos y temas relacionados (Proc. Conf., Univ. Waterloo, Waterloo, Ontario, 1977) , Nueva York: Academic Press, págs. 91–103, SEÑOR  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: Sociedad Matemática Estadounidense, págs. 371–376, doi :10.1090/conm/197/02534, SEÑOR  1411698.
• Coullard, Collette R .; Hellerstein, Lisa (1996), "Independencia y oráculos portuarios 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 intersección y partición matroide", SIAM Journal on Computing , 15 (4): 948–957, doi :10.1137/0215066, MR  0861361.
• Edmonds, Jack (1965), "Partición mínima de una matroide en subconjuntos independientes", Revista de investigación de la Oficina Nacional de Estándares , 69B : 67–72, doi : 10.6028/jres.069b.004 , MR  0190025.
• Edmonds, Jack (1971), "Matroides y el algoritmo codicioso", Programación matemática , 1 : 127–136, doi :10.1007/BF01584082, MR  0297357.
• Fujishige, Satoru; Zhang, Xiaodong (1995), "Un algoritmo eficiente de escalamiento de costos para el problema de asignación independiente", Revista de la Sociedad de Investigación de Operaciones de Japón , 38 (1): 124–136, SEÑOR  1337446.
• Hausmann, Dirk; Korte, Bernhard (1978), "Límites inferiores de la complejidad del peor de los casos de algunos algoritmos de Oracle", Matemáticas discretas , 24 (3): 261–276, doi : 10.1016/0012-365X(78)90097-3 , SEÑOR  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, SEÑOR  0600125.
• Ingleton, AW (1959), "Una nota sobre las funciones y el rango de independencia", Revista de la Sociedad Matemática de Londres , Segunda Serie, 34 : 49–56, doi :10.1112/jlms/s1-34.1.49, MR  0101848.
• Jensen, por M.; Korte, Bernhard (1982), "Complejidad de los algoritmos de propiedades matroides", SIAM Journal on Computing , 11 (1): 184–190, doi :10.1137/0211014, MR  0646772.
• Karp, Richard M .; Upfal, Elí ; 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, Alaska; Polesskiĭ, VP (1994), "Conjuntos extremos y problemas de cobertura y empaquetamiento en matroides", Temas seleccionados en matemáticas discretas (Moscú, 1972-1990) , Amer. Matemáticas. Soc. Traducción Ser. 2, vol. 158, Providencia, Rhode Island: Amer. Matemáticas. Soc., págs. 149-174, SEÑOR  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 geometrías", Journal of Combinatorial Theory , Serie A, 16 : 398–400, doi : 10.1016/0097-3165(74)90063-6 , MR  0335312.
• Korte, Bernhard; Hausmann, Dirk (1978), "Un análisis de la heurística codiciosa para los sistemas de independencia", 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, SEÑOR  0500689.
• Korté, B.; Schrader, R. (1981), "Un estudio sobre técnicas de oráculos", en Gruska, Jozef; Chytil, Michal (eds.), Mathematical Foundations of Computer Science 1981, Actas, décimo 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, SEÑOR  0652740.
• Lazarson, T. (1958), "El problema de representación de las funciones de independencia", Revista de la Sociedad Matemática de Londres , 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 matroide y descripciones no sucintas", Revista SIAM de Matemáticas Discretas , 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 , SEÑOR  2305892.
• Piff, MJ (1973), "Un límite superior para el número de matroides", Journal of Combinatorial Theory , Serie B, 14 : 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 las 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, SEÑOR  0008250.
• Rado, R. (1957), "Nota sobre las funciones de independencia", Actas de la Sociedad Matemática de Londres , 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 matroides", Procedimientos matemáticos de la Sociedad Filosófica de Cambridge , 87 (1): 29–45, Bibcode :1980MPCPS..87...29R, doi :10.1017/S0305004100056498, Señor  0549295.
• Seymour, PD (1981), "Reconocimiento de matroides gráficas", Combinatorica , 1 (1): 75–78, doi :10.1007/BF02579179, MR  0602418.
• Seymour, PD ; Walton, PN (1981), "Detecting matroid minors", Revista de la Sociedad Matemática de Londres , 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 de 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", Canadian Journal of Mathematics , 18 : 1301–1324, doi : 10.4153/CJM-1966-129-2 , MR  0205880.