Also known as interval thickness, node searching number, vertex separation number, pw(G), interval-width minus 1
In graph theory, a path decomposition of a graph is, informally, a representation of as a "thickened" path graph, and the pathwidth of is a number that measures how much the path was thickened to form . More formally, a path-decomposition is a sequence of subsets of vertices of such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness (one less than the maximum clique size
В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён. Более формально, путевая декомпозиция — это последовательности вершин подмножества графа G, такие, что конечные вершины каждого ребра появляются в одном из подмножеств и каждая вершина принадлежит (хотя бы) одному из множеств, а путевая ширина на единицу меньше размера наибольшего множества в такой декомпозиции.Путевая ширина известна также как интервальная толщина (на единицу меньше размера наибольшей клики интервального суперграфа графа G), величина вершинного разделения или вершинно-поисковое число. Путевая ширина и путевая декомпозиция являются тесной аналогией с древесной шириной и древесной декомпозицией. Они играют ключевую роль в теории миноров графа — семейства графов, замкнутых относительно миноров графа и не включающих все леса могут быть охарактеризованы как имеющие ограниченную путевую ширину, и «вихри», возникающие в общей структурной теорией семейств графов, замкнутых по минорам, имеют ограниченную путевую ширину. Путевая ширина и графы с ограниченной путевой шириной имеют приложение в разработке СБИС, визуализации графов и компьютерной лингвистике. Задача нахождения путевой ширины произвольных графов является NP-трудной. Более того, NP-трудна даже задача аппроксимации путевой ширины точно. Однако эта задача является — проверка, имеет ли граф путевую ширину k, может быть решена за время, которое линейно зависит от размера графа, но суперэкспоненциально от k Кроме того, для некоторых специальных классов графов, таких как деревья, путевая ширина может быть вычислена за полиномиальное время, независимое от k.Многие задачи теории графов можно эффективно решить на графах с ограниченной путевой шириной при помощи динамического программирования на путевой декомпозиции графа. Древесную декомпозицию можно также использовать для оценки алгоритмов динамического программирования на графах с ограниченной древесной шириной.
Abstract from DBpedia / Wikipedia · CC BY-SA
Discovered by embedding cosine similarity (sentence-transformers MiniLM, 384-dim).