Матроид оракул - Matroid oracle

В математике и информатике матроид оракул это подпрограмма через который алгоритм может получить доступ к матроид, абстрактная комбинаторная структура, которая может быть использована для описания линейные зависимости между векторами в векторное пространство или остовные деревья из график, среди других приложений.

Наиболее часто используемый оракул этого типа - это оракул независимости, подпрограмма для проверки того, является ли набор элементов матроида независимым. Также использовались несколько других типов оракулов; Некоторые из них оказались слабее, чем оракулы независимости, некоторые сильнее, а некоторые эквивалентны по вычислительной мощности.^[1]

Много алгоритмы которые выполняют вычисления на матроидах, были спроектированы так, чтобы принимать на входе оракул, что позволяет им эффективно работать без изменений на многих различных типах матроидов и без дополнительных предположений о том, какой матроид они используют. Например, учитывая оракул независимости для любого матроида, можно найти базис минимального веса матроида, применяя жадный алгоритм который добавляет элементы в основу в отсортированном порядке по весу, используя оракул независимости, чтобы проверить, можно ли добавить каждый элемент.^[2]

В теория сложности вычислений, то модель оракула привело к безусловному нижняя граница доказывая, что некоторые задачи матроидов не могут быть решены за полиномиальное время, без использования недоказанных предположений, таких как предположение, что P ≠ NP. Проблемы, которые оказались сложными таким образом, включают проверку того, является ли матроид двоичный или же униформа, или проверка наличия определенных фиксированных несовершеннолетние.^[3]

Почему оракулы?

Хотя некоторые авторы экспериментировали с компьютерными представлениями матроидов, которые явно перечисляют все независимые наборы или все базисные наборы матроидов,^[4] эти представления не лаконичный: матроид с ${\displaystyle \scriptstyle n}$ элементы могут расширяться в представление, которое занимает пространство экспоненциально в ${\displaystyle \scriptstyle n}$. Действительно, количество различных матроидов на ${\displaystyle \scriptstyle n}$ элементы растут вдвойне экспоненциально в качестве

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

из чего следует, что любое явное представление, способное обрабатывать все возможные матроиды, обязательно будет использовать экспоненциальное пространство.^[6]

Вместо этого различные типы матроидов могут быть представлены более эффективно из других структур, из которых они определены: однородные матроиды из их двух числовых параметров, графические матроиды, двукруглые матроиды, и гаммоиды из графиков, линейные матроиды из матрицы и т. д. Однако алгоритм для выполнения вычислений на произвольных матроидах нуждается в унифицированном методе доступа к его аргументу, а не в перепроектировании каждого из этих классов матроидов. Модель оракула предоставляет удобный способ кодификации и классификации видов доступа, которые могут понадобиться алгоритму.

История

Начиная с Rado (1942), "функции независимости" или "${\displaystyle \scriptstyle I}$-функции »были изучены как один из многих эквивалентных способов аксиоматизации матроидов. Функция независимости отображает набор элементов матроида на число ${\displaystyle \scriptstyle 1}$ если набор независимый или ${\displaystyle \scriptstyle 0}$ если он иждивенец; то есть это индикаторная функция семейства независимых множеств, по сути то же самое, что оракул независимости.^[7]

Оракулы Matroid также были частью самой ранней алгоритмической работы над матроидами. Таким образом, Эдмондс (1965), при изучении проблем разбиения матроида, предположил, что доступ к данному матроиду осуществляется через подпрограмму, которая принимает на вход независимый набор ${\displaystyle \scriptstyle I}$ и элемент ${\displaystyle \scriptstyle x}$, и либо возвращает схему в ${\displaystyle \scriptstyle I\cup \{x\}}$ (обязательно уникальный и содержащий ${\displaystyle \scriptstyle x}$, если он существует) или определяет, что такой схемы не существует. Эдмондс (1971) использовал подпрограмму, которая проверяет, является ли данный набор независимым (то есть, в более современной терминологии, оракул независимости), и заметил, что предоставляемой информации достаточно, чтобы найти базис минимального веса за полиномиальное время.

Начиная с работы Корте и Хаусманн (1978) иХаусманн и Корте (1978), исследователи начали изучать оракулы с точки зрения доказательства нижних оценок алгоритмов для матроидов и связанных структур. Эти две статьи Хаусмана и Корте касались проблемы поиска независимого от максимальной мощности множества, что легко для матроидов, но (как они показали) труднее аппроксимировать или точно вычислить для более общих системы независимости представлен оракулом независимости. Эта работа положила начало целому ряду статей в конце 1970-х - начале 1980-х годов, показывающих аналогичные результаты по твердости для задач на матроидах.^[8] и сравнивая возможности различных видов матроидных оракулов.^[9]

С тех пор оракул независимости стал стандартом для большинства исследований алгоритмов матроидов.^[10] Также были продолжены исследования по нижним оценкам,^[11] и сравнения разных типов оракулов.^[12]

Типы оракулов

Были рассмотрены следующие типы оракулов матроидов.

• An оракул независимости принимает на входе набор элементов матроида и возвращает на выходе Логическое значение, истина, если данное множество является независимым, и ложь в противном случае.^[13] Его можно легко реализовать на основе базовой структуры, из которой был определен матроид для графические матроиды, поперечные матроиды, гаммоиды, и линейные матроиды, а также для матроидов, образованных из них стандартными операциями, такими как прямые суммы.^[3]
• Оракул из Эдмондс (1965) принимает в качестве входных данных независимый набор и дополнительный элемент и либо определяет, что их объединение является независимым, либо находит схему в объединении и возвращает ее.
• А ранг оракула принимает на вход набор элементов матроида и возвращает на выходе числовое значение, классифицировать данного набора.^[9]
• А основа оракула принимает в качестве входных данных набор элементов матроида и возвращает в качестве выходных данных логическое значение: истина, если данный набор является базисом, и ложь в противном случае.^[9]
• А круговой оракул принимает в качестве входных данных набор элементов матроида и возвращает в качестве выходных данных логическое значение: истина, если данный набор является схемой, и ложь в противном случае.^[9]
• Три типа закрытие оракула были рассмотрены: один, который проверяет, принадлежит ли данный элемент к замыканию данного набора, второй, который возвращает закрытие набора, и третий, который проверяет, является ли данный набор закрытым.^[9]
• А охватывающий оракул принимает в качестве входных данных набор элементов матроида и возвращает в качестве выходных данных логическое значение, истина, если данный набор является охватывающим (т.е. содержит базис и имеет тот же ранг, что и весь матроид), и ложь в противном случае.^[14]
• А обхват оракула принимает на вход набор элементов матроида и возвращает на выходе числовое значение, размер наименьшей схемы в этом наборе (или ${\displaystyle \scriptstyle +\infty }$ если данный набор независим).^[14]
• А порт оракул для фиксированного элемента ${\displaystyle \scriptstyle x}$ матроида принимает на вход набор элементов матроида и возвращает на выходе логическое значение, истина, если данный набор содержит схему, которая включает ${\displaystyle \scriptstyle x}$ и false в противном случае.^[15]

Относительная сила разных оракулов

Хотя существует много известных типов оракулов, выбор которых можно упростить, поскольку многие из них эквивалентны по вычислительной мощности. Оракул ${\displaystyle \scriptstyle X}$ как говорят полиномиально приводимый к другому оракулу ${\displaystyle \scriptstyle Y}$ если есть звонок ${\displaystyle \scriptstyle X}$ может быть смоделирован алгоритмом, который обращается к матроиду, используя только оракул ${\displaystyle \scriptstyle Y}$ и берет полиномиальное время измеряется количеством элементов матроида; в терминах теории сложности это Редукция Тьюринга. Говорят, что два оракула полиномиально эквивалентный если они полиномиально сводятся друг к другу. Если ${\displaystyle \scriptstyle X}$ и ${\displaystyle \scriptstyle Y}$ полиномиально эквивалентны, то каждый результат, который доказывает существование или отсутствие алгоритма полиномиального времени для задачи матроида с использованием оракула ${\displaystyle \scriptstyle X}$ также доказывает то же самое для оракула ${\displaystyle \scriptstyle Y}$.

Например, оракул независимости полиномиально эквивалентен оракулу поиска схемы Эдмондс (1965). Если доступен оракул для поиска схем, набор можно проверить на независимость, используя не более ${\displaystyle \scriptstyle n}$ взывает к оракулу, начиная с пустой набор, добавляя элементы данного набора по одному элементу за раз, и используя оракул поиска схем, чтобы проверить, сохраняет ли каждое добавление независимость набора, который был построен на данный момент. В противном случае, если доступен оракул независимости, схема в наборе ${\displaystyle \scriptstyle I\cup \{x\}}$ можно найти с использованием не более ${\displaystyle \scriptstyle n}$ вызывает оракул путем тестирования для каждого элемента ${\displaystyle \scriptstyle y\in I}$, ли ${\displaystyle \scriptstyle I\setminus \{y\}\cup \{x\}}$ является независимым и возвращает элементы, для которых ответ отрицательный. Оракул независимости также полиномиально эквивалентен оракулу ранга, покрывающему оракулу, первым двум типам оракула закрытия и оракулу порта.^[1]

Базовый оракул, схемный оракул и оракул, который проверяет, является ли данный набор замкнутым, все слабее, чем оракул независимости: они могут быть смоделированы за полиномиальное время с помощью алгоритма, который обращается к матроиду с помощью оракула независимости, но не наоборот . Кроме того, ни один из этих трех оракулов не может имитировать друг друга за полиномиальное время. В том же смысле обхват оракула сильнее оракула независимости.^[9]

Помимо полиномиального времени редукции Тьюринга, были рассмотрены и другие типы сводимости. Особенно, Карп, Упфал и Вигдерсон (1988) показал, что в параллельные алгоритмы, оракулы ранга и независимости существенно различаются по вычислительной мощности. Оракул рангов позволяет построить базис минимального веса с помощью ${\displaystyle \scriptstyle n}$ одновременные запросы префиксов отсортированного порядка элементов матроида: элемент принадлежит оптимальному базису тогда и только тогда, когда ранг его префикса отличается от ранга предыдущего префикса. Напротив, поиск минимального базиса с оракулом независимости происходит намного медленнее: его можно решить детерминированно в ${\displaystyle \scriptstyle O({\sqrt {n}})}$ шагов по времени, и существует нижняя граница ${\displaystyle \scriptstyle \Omega ((n/\log n)^{1/3})}$ даже для рандомизированных параллельных алгоритмов.

Алгоритмы

Известно, что многие проблемы на матроидах решаются в полиномиальное время алгоритмами, которые обращаются к матроиду только через оракул независимости или другой оракул эквивалентной мощности, без каких-либо дополнительных предположений о том, какой матроид им был дан. К этим полиномиально решаемым задачам относятся:

• Нахождение минимального или максимального веса взвешенный матроид, используя жадный алгоритм.^[2]
• Разделение элементов матроида на минимальное количество независимых наборов и поиск самого большого набора, который одновременно является независимым в двух заданных матроидах. Последняя проблема называется пересечение матроидов, и решения обеих проблем тесно связаны друг с другом.^[16]
• Тестирование матроида ${\displaystyle \scriptstyle k}$-связанный (в смысле Тутт 1966 ) за ${\displaystyle \scriptstyle k\leq 3}$.^[17]
• Проверка того, является ли данный матроид графический^[18] или же обычный.^[19]
• Нахождение разложение уха данного матроида, последовательность схем, объединение которых является матроидом, и в которой каждая схема остается схемой после сжатия всех предыдущих схем в последовательности. Такое разложение можно также найти с дополнительным свойством, что выбранный элемент матроида принадлежит каждой схеме.^[15]
• Нахождение ветвление-разложение данного матроида, если его ширина ветви не больше фиксированной константы.^[20]
• Перечисление всех баз, квартир или схем матроида за полиномиальное время для каждого выходного набора.^[21]
• Приближая количество оснований полностью полиномиальная схема рандомизированной аппроксимации, для матроида с ${\displaystyle \scriptstyle n}$ элементы и ранг ${\displaystyle \scriptstyle r}$, с дополнительным предположением, что количество оснований находится в пределах полиномиального множителя количества ${\displaystyle \scriptstyle r}$-элементные наборы.^[22]

Доказательства невозможности

Для многих задач матроидов можно показать, что оракул независимости не обеспечивает достаточной мощности, чтобы позволить решить проблему за полиномиальное время. Основная идея этих доказательств - найти два матроида. ${\displaystyle \scriptstyle M}$ и ${\displaystyle \scriptstyle M'}$ от которых зависит ответ на проблему и которые алгоритму трудно различить. В частности, если ${\displaystyle \scriptstyle M}$ обладает высокой степенью симметрии и отличается от ${\displaystyle \scriptstyle M'}$ только в ответах на небольшое количество запросов, тогда может потребоваться очень большое количество запросов для алгоритма, чтобы быть уверенным в различении ввода типа ${\displaystyle \scriptstyle M}$ от входа, сформированного с использованием одной из симметрий ${\displaystyle \scriptstyle M}$ переставлять ${\displaystyle \scriptstyle M'}$.^[3]

На простом примере этого подхода можно показать, что трудно проверить, является ли матроид униформа. Пусть для простоты изложения ${\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)}$

запросы независимости, намного превышающие полиномиальные. Даже рандомизированный алгоритм должен сделать примерно столько же запросов, чтобы быть уверенным в различении этих двух матроидов.^[23]

Дженсен и Корте (1982) формализовать этот подход, доказав, что если существуют два матроида ${\displaystyle \scriptstyle M}$ и ${\displaystyle \scriptstyle M'}$ на одном и том же наборе элементов, но с разными ответами на проблемы, алгоритм, который правильно решает данную проблему на этих элементах, должен использовать как минимум

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

запросы, где ${\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!}$.^[24]

Проблемы, которые оказались невозможными для алгоритма оракула матроида для вычисления за полиномиальное время, включают:

• Проверка однородности данного матроида.^[23]
• Проверка, содержит ли данный матроид фиксированный матроид ${\displaystyle \scriptstyle H}$ как несовершеннолетний, за исключением особых случаев, когда ${\displaystyle \scriptstyle H}$ одинаков с рангом или корангом не более одного. В более общем смысле, если ${\displaystyle \scriptstyle {\mathcal {H}}}$ - фиксированный конечный набор матроидов, и в ${\displaystyle \scriptstyle {\mathcal {H}}}$, то невозможно проверить за полиномиальное время, содержит ли данный матроид один или несколько матроидов в ${\displaystyle \scriptstyle {\mathcal {H}}}$ как несовершеннолетний.^[25]
• Проверка того, является ли данный матроид двоичный, представима над любым конкретным фиксированным поле, или существует ли поле, над которым он может быть представлен.^[26]
• Решение задачи сопоставления матроидов, в которой входными данными является граф и матроид в его вершинах, а цель - найти соответствие в графе, который является как можно большим, при условии, что совпадающие вершины образуют независимый набор.^[27]
• Проверка того, является ли данный матроид самодвойственный, поперечный, двудольный, Эйлеров, или же ориентируемый.^[3]
• Вычисление обхвата (размера наименьшего контура), размера наибольшего контура, количества контуров, количества оснований, количества квартир, количества квартир максимального ранга, размера самой большой квартиры, Полином Тутте, или возможность подключения данного матроида.^[3]

Среди множества всех свойств ${\displaystyle \scriptstyle n}$-элементных матроидов, доля свойств, для проверки которых не требуется экспоненциальное время, стремится к нулю в пределе, как ${\displaystyle \scriptstyle n}$ уходит в бесконечность.^[6]

Смотрите также

• Группа черного ящика, подобная оракулу модель для теория групп
• Неявный граф, подобная оракулу модель для алгоритмов графа

Примечания

1. Робинсон и валлийский (1980); Хаусманн и Корте (1981); Куллар и Хеллерштейн (1996).
2. Эдмондс (1971).
3. Дженсен и Корте (1982).
4. Мэйхью (2008).
5. Пифф и валлийский (1971); Пифф (1973); Кнут (1974); Бансал, Пендавинг и ван дер Поль (2012).
6. Робинсон и валлийский (1980).
7. Дополнительные исследования матроидов, основанные на аксиоматизации функции независимости, см., Например, Rado (1957), Лазарсон (1958), и Инглтон (1959).
8. Ловас (1981); Сеймур (1981); Сеймур и Уолтон (1981); Дженсен и Корте (1982); Truemper (1982).
9. Робинсон и валлийский (1980); Хаусманн и Корте (1981).
10. Например. видеть Каннингем (1986), Кельманс и Полесский (1994) Фуджишигэ и Чжан (1995), Чавес Ломели и валлийский (1996), Хачиян и др. (2005), и Оум и Сеймур (2007).
11. Азар, Бродер и Фриз (1994).
12. Карп, Упфал и Вигдерсон (1988); Куллар и Хеллерштейн (1996).
13. Эдмондс (1971); Робинсон и валлийский (1980); Хаусманн и Корте (1981).
14. Хаусманн и Корте (1981).
15. Куллар и Хеллерштейн (1996).
16. Эдмондс (1965); Каннингем (1986).
17. Биксби и Каннингем (1979). Статья, в которой утверждается аналогичный результат для любой фиксированной константы ${\displaystyle \scriptstyle k}$ был объявлен Каннингемом и Эдмондсом примерно в то же время, но, похоже, не был опубликован. Truemper (1998), pp. 186–187, пишет "Locating ${\displaystyle \scriptstyle k}$-суммы для общих ${\displaystyle \scriptstyle k\geq 4}$ намного сложнее ... Мы не знаем, как это может быть эффективно выполнено для бинарных матроидов, не говоря уже об обычных матроидах ".
18. Сеймур (1981).
19. Truemper (1982).
20. Оум и Сеймур (2007).
21. Хачиян и др. (2005).
22. Чавес Ломели и валлийский (1996). Напротив, детерминированные алгоритмы не могут точно аппроксимировать количество оснований матроида за полиномиальное время (Азар, Бродер и Фриз 1994 ).
23. Робинсон и валлийский (1980); Дженсен и Корте (1982).
24. Как и в Дженсен и Корте (1982), эта формализация рассматривается в Корте и Шредер (1981). В большинстве случаев применения этой техники в Дженсен и Корте (1982), ${\displaystyle \scriptstyle M}$ единообразно, но Сеймур (1981) применяет ту же идею к неоднородному, но высокосимметричному матроиду.
25. Сеймур и Уолтон (1981). Результаты Сеймур (1981) и Дженсен и Корте (1982) приведите частные случаи этого для задач поиска ${\displaystyle \scriptstyle U{}_{4}^{2}}$ несовершеннолетний и Вамос матроид минор соответственно. Проверка того, является ли матроид графическим или регулярным, может быть выражена в терминах конечного набора запрещенных миноров и может быть решена за полиномиальное время, но запрещенные миноры для этих задач включают однородный матроид ${\displaystyle \scriptstyle U{}_{4}^{2}}$, поэтому они не противоречат этому результату о невозможности.
26. Сеймур (1981) показал это для бинарных матроидов, Сеймур и Уолтон (1981) для конечных полей Truemper (1982) для произвольных полей и Дженсен и Корте (1982) для существования поля, над которым матроид представим.
27. Ловас (1981); Дженсен и Корте (1982). Однако частный случай этой проблемы для двудольные графы может быть решена за полиномиальное время как пересечение матроидов проблема.

Рекомендации

• Azar, Y .; Бродер, А.З.; Фриз, А.М. (1994), "К проблеме аппроксимации числа оснований матроида", Письма об обработке информации, 50 (1): 9–11, Дои:10.1016 / 0020-0190 (94) 90037-X, МИСТЕР  1279491.
• Bansal, N .; Pendavingh, R .; ван дер Поль, Дж. (2012), О количестве матроидов, arXiv:1206.6270, Bibcode:2012arXiv1206.6270B.
• Биксби, Роберт Э .; Каннингем, Уильям Х. (1979), «Матроиды, графики и 3-связность», Теория графов и смежные вопросы (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977), Нью-Йорк: Academic Press, стр. 91–103, МИСТЕР  0538038.
• Чавес Ломели, Лаура; Валлийский, доминик (1996), "Рандомизированная аппроксимация числа оснований", Теория матроидов (Сиэтл, Вашингтон, 1995), Современная математика, 197, Провиденс, Род-Айленд: Американское математическое общество, стр. 371–376, Дои:10.1090 / conm / 197/02534, МИСТЕР  1411698.
• Coullard, Collette R.; Хеллерштейн, Лиза (1996), "Независимость и портированные оракулы для матроидов, с приложением к теории вычислительного обучения", Комбинаторика, 16 (2): 189–208, Дои:10.1007 / BF01844845, МИСТЕР  1401892.
• Каннингем, Уильям Х. (1986), "Улучшенные оценки для алгоритмов разбиения и пересечения матроидов", SIAM Журнал по вычислениям, 15 (4): 948–957, Дои:10.1137/0215066, МИСТЕР  0861361.
• Эдмондс, Джек (1965), «Минимальное разбиение матроида на независимые подмножества», Журнал исследований Национального бюро стандартов, 69B: 67–72, Дои:10.6028 / jres.069b.004, МИСТЕР  0190025.
• Эдмондс, Джек (1971), «Матроиды и жадный алгоритм», Математическое программирование, 1: 127–136, Дои:10.1007 / BF01584082, МИСТЕР  0297357.
• Фудзишигэ, Сатору; Чжан, Сяодун (1995), "Эффективный алгоритм масштабирования затрат для задачи независимого назначения", Журнал Общества исследования операций Японии, 38 (1): 124–136, МИСТЕР  1337446.
• Хаусманн, Дирк; Корте, Бернхард (1978), "Нижние оценки наихудшей сложности некоторых алгоритмов оракула", Дискретная математика, 24 (3): 261–276, Дои:10.1016 / 0012-365X (78) 90097-3, МИСТЕР  0523316.
• Hausmann, D .; Корте, Б. (1981), "Алгоритмические и аксиоматические определения матроидов", Математическое программирование в Обервольфахе (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979), Математическое программирование, 14, стр. 98–111, Дои:10.1007 / BFb0120924, МИСТЕР  0600125.
• Инглтон, A. W. (1959), "Заметка о функциях независимости и ранге", Журнал Лондонского математического общества, Вторая серия, 34: 49–56, Дои:10.1112 / jlms / s1-34.1.49, МИСТЕР  0101848.
• Jensen, Per M .; Корте, Бернхард (1982), "Сложность алгоритмов свойств матроидов", SIAM Журнал по вычислениям, 11 (1): 184–190, Дои:10.1137/0211014, МИСТЕР  0646772.
• Карп, Ричард М.; Упфаль, Эли; Вигдерсон, Ави (1988), «Сложность параллельного поиска», Журнал компьютерных и системных наук, 36 (2): 225–253, Дои:10.1016 / 0022-0000 (88) 90027-Х, МИСТЕР  0950432.
• Кельманс, А. К .; Полесский В. П. (1994), "Экстремальные множества, задачи покрытия и упаковки в матроидах", Избранные темы дискретной математики (Москва, 1972–1990), Амер. Математика. Soc. Пер. Сер. 2, 158, Провиденс, Род-Айленд: амер. Математика. Soc., Стр. 149–174, МИСТЕР  1269136.
• Хачиян, Л.; Boros, E .; Эльбассиони, К .; Гурвич, В .; Макино, К. (2005), "О сложности некоторых задач перечисления матроидов", Журнал SIAM по дискретной математике, 19 (4): 966–984, CiteSeerX  10.1.1.124.4286, Дои:10.1137 / S0895480103428338, МИСТЕР  2206374.
• Кнут, Дональд Э. (1974), «Асимптотическое число геометрий», Журнал комбинаторной теории, Серия А, 16: 398–400, Дои:10.1016/0097-3165(74)90063-6, МИСТЕР  0335312.
• Корте, Бернхард; Хаусманн, Дирк (1978), "Анализ жадной эвристики для систем независимости", Алгоритмические аспекты комбинаторики (конференция, остров Ванкувер, Британская Колумбия, 1976), Анналы дискретной математики, 2, стр. 65–74, Дои:10.1016 / S0167-5060 (08) 70322-4, МИСТЕР  0500689.
• Корте, Б ​​.; Schrader, R. (1981), "Обзор методов оракула", в Gruska, Jozef; Chytil, Michal (ред.), Математические основы информатики 1981, Труды 10-го симпозиума Штрбске Плесо, Чехословакия 31 августа - 4 сентября 1981 г., Конспект лекций по информатике, 118, Берлин: Springer, стр. 61–77, Дои:10.1007/3-540-10856-4_74, МИСТЕР  0652740.
• Лазарсон, Т. (1958), "Проблема представления для функций независимости", Журнал Лондонского математического общества, Вторая серия, 33: 21–25, Дои:10.1112 / jlms / s1-33.1.21, МИСТЕР  0098701.
• Ловас, Л. (1981), "Задача сопоставления матроидов", Алгебраические методы в теории графов, Vol. I, II (Сегед, 1978), Коллок. Математика. Soc. Янош Бойяи, 25, Амстердам: Северная Голландия, стр. 495–517, МИСТЕР  0642059.
• Мэйхью, Диллон (2008 г.), «Сложность матроидов и нечеткие описания», Журнал SIAM по дискретной математике, 22 (2): 455–466, arXiv:математика / 0702567, Дои:10.1137/050640576, МИСТЕР  2399359.
• Оум, Санг-ил; Сеймур, Пол (2007), «Тестирование ширины ветки», Журнал комбинаторной теории, Серия B, 97 (3): 385–393, Дои:10.1016 / j.jctb.2006.06.006, МИСТЕР  2305892.
• Пифф, М. Дж. (1973), "Верхняя оценка числа матроидов", Журнал комбинаторной теории, Серия B, 14: 241–245, Дои:10.1016/0095-8956(73)90006-3, МИСТЕР  0316282.
• Piff, M. J .; Валлийский, Д. Дж. А. (1971), «Число комбинаторных геометрий», Бюллетень Лондонского математического общества, 3: 55–56, Дои:10.1112 / blms / 3.1.55, МИСТЕР  0282867.
• Радо, Р. (1942), «Теорема об отношениях независимости», Ежеквартальный журнал математики, Вторая серия, 13: 83–89, Bibcode:1942QJМат..13 ... 83R, Дои:10.1093 / qmath / os-13.1.83, МИСТЕР  0008250.
• Радо, Р. (1957), «Заметка о функциях независимости», Труды Лондонского математического общества, Третья серия, 7: 300–320, Дои:10.1112 / плмс / с3-7.1.300, МИСТЕР  0088459.
• Робинсон, Г. С .; Валлийский, Д. Дж. А. (1980), «Вычислительная сложность свойств матроидов», Математические труды Кембриджского философского общества, 87 (1): 29–45, Bibcode:1980MPCPS..87 ... 29R, Дои:10.1017 / S0305004100056498, МИСТЕР  0549295.
• Сеймур, П.Д. (1981), "Распознавание графических матроидов", Комбинаторика, 1 (1): 75–78, Дои:10.1007 / BF02579179, МИСТЕР  0602418.
• Сеймур, П.Д.; Уолтон, П. Н. (1981), "Обнаружение несовершеннолетних матроидов", Журнал Лондонского математического общества, Вторая серия, 23 (2): 193–203, Дои:10.1112 / jlms / s2-23.2.193, МИСТЕР  0609098.
• Truemper, K. (1982), "Об эффективности тестов представимости для матроидов", Европейский журнал комбинаторики, 3 (3): 275–291, Дои:10.1016 / s0195-6698 (82) 80039-5, МИСТЕР  0679212.
• Трумпер, К. (1998), Разложение Matroid (PDF) (переработанная ред.).
• Тутте, В. Т. (1966), «Связь в матроидах», Канадский математический журнал, 18: 1301–1324, Дои:10.4153 / CJM-1966-129-2, МИСТЕР  0205880.