Зада́ча о незави́симом мно́жестве относится к классу NP-полных задач в области теории графов. Эквивалентна задаче о клике.
В математике, приближенная схема полиномиального времени или polynomial-time approximation scheme (PTAS) обозначает класс приближенных полиномиальных по времени выполнения алгоритмов для решения, как правило, NP-трудных оптимизационных задач. Если P = NP, то введение этого понятия теряет смысл. Поэтому далее будем предполагать, что Р не совпадает с NР. И без ограничения общности определим понятие для задачи минимизации.
Класс APX в теории вычислительной сложности — это класс NP-трудных задач, для которых существуют аппроксимационные алгоритмы полиномиальной сложности с постоянным коэффициентом аппроксимации. В более простых терминах, задачи этого класса имеют эффективные алгоритмы, находящие решения, которые хуже оптимального не более чем на фиксированный процент. Например, существует алгоритм полиномиальной сложности для решения задачи об упаковке в контейнеры, который использует не более чем на 5 % больше контейнеров, чем наименьшее необходимое их число.
Аппроксимационный алгоритм — в исследовании операций алгоритм, использующийся для поиска приближённого решения оптимизационной задачи.
В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы.
В теории графов доминирующее множество для графа G = (V, E) — это подмножество D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D. Число доминирования γ(G) — это число вершин в наименьшем доминирующем множестве G.
Упаковка множеств — это классическая NP-полная задача в теории вычислительной сложности и комбинаторике и является одной из 21 NP-полных задач Карпа.
Максимальный разрез графа — это разрез, размер которого не меньше размера любого другого разреза. Задача определения максимального разреза для графа известна как задача о максимальном разрезе.
В теории графов доминирующее множество рёбер (или рёберное доминирующее множество) графа G = (V, E) — это подмножество D ⊆ E, такое, что любое ребро не из D смежно по меньшей мере одному ребру из D. На рисунках (a)–(d) приведены примеры доминирующих множеств рёбер (красные рёбра).
Алгоритм Хопкрофта — Карпа — алгоритм, принимающий на вход двудольный граф и возвращающий максимальное по мощности паросочетание, то есть наибольшее множество рёбер, таких что никакие два не имеют общую вершину. Асимптотика времени работы алгоритма составляет 
в худшем случае. В случае плотных графов время работы ограничивается 
, а для случайного графа алгоритм работает почти за линейное время.
Теорема о планарном разбиении — это форма изопериметрического неравенства для планарных графов, которое утверждает, что любой планарный граф может быть разбит на более мелкие части путём удаления небольшого числа вершин. В частности, удалением O(√n) вершин из графа с n вершинами можно разбить граф на несвязные подграфы, каждый из которых имеет не более 2n/3 вершин.
Наименьший k-разрез — это задача комбинаторной оптимизации, в которой требуется найти множество рёбер, удаление которых разбивает граф на k связных компонент. Эти рёбра называются k-разрезом. Целью задачи является поиск k-разреза с минимальным весом. Такое разбиение может иметь приложения при разработке СБИС, интеллектуальном анализе данных, в методе конечных элементов и информационном обмене при параллельных вычислениях.
Связное доминирующее множество и остовное дерево с максимальной листвой являются двумя тесно связанными структурами, определёнными на неориентированном графе.
Расстояние редактирования графа — это коэффициент сходства между двумя графами. Концепцию расстояния редактирования графа впервые сформулировали математически Альберто Санфелиу и Кинг-Сан Фу в 1983. Главное приложение расстояния редактирования графа — в неточном сопоставлении графов, таких как устойчивое распознавание образов в машинном обучении.
Неориентированный граф G двойственно хордален, если гиперграф его максимальных клик является гипердеревом. Имя происходит из факта, что граф хордален тогда и только тогда, когда гиперграф его максимальных клик двойственен гипердереву. Первоначально эти графы были определены по максимальному соседству и имеют ряд различных описаний. В отличие от хордальных графов свойство двойственной хордальности не наследуется, то есть, порождённые подграфы двойственного хордального графа не обязательно двойственно хордальны, и двойственно хордальный граф в общем случае не совершенный. Двойственно хордальные графы появились первоначально под именем HT-графы.
Алгоритм Кристофидеса или алгоритм Кристофидеса-Сердюкова — это алгоритм поиска приближённых решений задачи коммивояжёра для случаев, когда расстояния образуют метрическое пространство . Алгоритм является аппроксимационным алгоритмом, который гарантирует, что решения находятся в пределах 3/2 от длины оптимального решения. Алгоритм назван именем Никоса Кристофидеса и Анатолия Ивановича Сердюкова, которые независимо друг от друга нашли его в 1976, и он обладает лучшим аппроксимационным коэффициентом, который был доказан для задачи коммивояжёра на метрических пространствах общего вида, хотя известны лучшие приближения для некоторых специальных случаев.
Послойное рисование графа или иерархическое рисование графа — это способ визуализации графов, в котором вершины ориентированного графа рисуются горизонтальными рядами или слоями с рёбрами, преимущественно направленными вниз. Такой способ известен как стиль Сугиямы визуализации графов, по имени Козо Сугиямы, который первым разрабатывал этот стиль.
Эстер Аркин — израильско-американский математик и учёный-информатик, чьи исследовательские интересы включают исследование операций, вычислительную геометрию, комбинаторную оптимизацию, а также разработку и анализ алгоритмов. Она профессор прикладной математики и статистики в Университете штата Нью-Йорк в Стони Бруке. В Стони Бруке она также руководит программой бакалавриата по прикладной математике и статистике и является аффилированным преподавателем кафедры компьютерных наук.
Александр Зиновьевич Зеликовский — молдавский и американский математик и информатик, заслуженный профессор Университетa штата Джорджия.
