| dbo:abstract
|
- Die Pfadweite oder Wegweite ist ein Begriff aus der Graphentheorie. Sie sagt aus, wie „pfad-ähnlich“ ein Graph ist. Da viele Algorithmen auf Pfaden (oder Pfadzerlegungen) effizient laufen, die dies auf allgemeinen Graphen nicht tun, ist es interessant, die Pfadweite zu kennen. Ein verwandter Begriff ist die Baumweite. (de)
- In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G 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 in an interval supergraph of G), vertex separation number, or node searching number. Pathwidth and path-decompositions are closely analogous to treewidth and tree decompositions. They play a key role in the theory of graph minors: the families of graphs that are closed under graph minors and do not include all forests may be characterized as having bounded pathwidth, and the "vortices" appearing in the general structure theory for minor-closed graph families have bounded pathwidth. Pathwidth, and graphs of bounded pathwidth, also have applications in VLSI design, graph drawing, and computational linguistics. It is NP-hard to find the pathwidth of arbitrary graphs, or even to approximate it accurately. However, the problem is fixed-parameter tractable: testing whether a graph has pathwidth k can be solved in an amount of time that depends linearly on the size of the graph but superexponentially on k. Additionally, for several special classes of graphs, such as trees, the pathwidth may be computed in polynomial time without dependence on k.Many problems in graph algorithms may be solved efficiently on graphs of bounded pathwidth, by using dynamic programming on a path-decomposition of the graph. Path decomposition may also be used to measure the space complexity of dynamic programming algorithms on graphs of bounded treewidth. (en)
- В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён. Более формально, путевая декомпозиция — это последовательности вершин подмножества графа G, такие, что конечные вершины каждого ребра появляются в одном из подмножеств и каждая вершина принадлежит (хотя бы) одному из множеств, а путевая ширина на единицу меньше размера наибольшего множества в такой декомпозиции.Путевая ширина известна также как интервальная толщина (на единицу меньше размера наибольшей клики интервального суперграфа графа G), величина вершинного разделения или вершинно-поисковое число. Путевая ширина и путевая декомпозиция являются тесной аналогией с древесной шириной и древесной декомпозицией. Они играют ключевую роль в теории миноров графа — семейства графов, замкнутых относительно миноров графа и не включающих все леса могут быть охарактеризованы как имеющие ограниченную путевую ширину, и «вихри», возникающие в общей структурной теорией семейств графов, замкнутых по минорам, имеют ограниченную путевую ширину. Путевая ширина и графы с ограниченной путевой шириной имеют приложение в разработке СБИС, визуализации графов и компьютерной лингвистике. Задача нахождения путевой ширины произвольных графов является NP-трудной. Более того, NP-трудна даже задача аппроксимации путевой ширины точно. Однако эта задача является — проверка, имеет ли граф путевую ширину k, может быть решена за время, которое линейно зависит от размера графа, но суперэкспоненциально от k Кроме того, для некоторых специальных классов графов, таких как деревья, путевая ширина может быть вычислена за полиномиальное время, независимое от k.Многие задачи теории графов можно эффективно решить на графах с ограниченной путевой шириной при помощи динамического программирования на путевой декомпозиции графа. Древесную декомпозицию можно также использовать для оценки алгоритмов динамического программирования на графах с ограниченной древесной шириной. (ru)
- Em teoria dos grafos, uma decomposição em caminho de um grafo G é, informalmente, uma representação de G como um caminho "alargado", e o pathwidth ou largura de caminho de G é um número que mede quanto o caminho foi ampliado em largura a partir de G. Mais formalmente, decomposição em caminho é uma sequência de subconjuntos de vértices de G em que os nós extremos de cada aresta apareçam em um dos subconjuntos e que cada vértice apareça em uma subsequência adjacente dos subconjuntos, e a largura de caminho é um a menos que o tamanho do maior conjunto em dada decomposição. Largura de caminho é também conhecida como largura de intervalo (um a menos que o tamanho do clique máximo em um de de G), número de separação de vértice, ou número de busca de nós. Largura de caminho e decomposições em caminho são aproximadamente análogos a e . Têm um papel fundamental na teoria de menores de grafos: as famílias de grafos que são fechadas sob menores de grafos e não incluem todas florestas devem ser caracterizadas como tendo caminhos de largura delimitados, e os "vórtices" aparecendo na tem caminhos de largura delimitados. Largura de caminho, e grafos de largura de caminho delimitados, possuem também aplicações em design de , , and linguística computacional. É NP-difícil encontrar a largura de caminho de grafos arbitrários, ou até mesmo fazer uma aproximação precisa. De qualquer maneira, o problema é tratável por parâmetro fixo: testando se um grafo de largura de caminho k pode ser resolvido em uma quantidade de tempo que depende linearmente do tamanho do grafo mas super-exponencialmente em k. Além disso, para várias classes especiais de grafos, como árvores, a largura de caminho pode ser computada em tempo polinomial sem dependência em k.Muitos problemas em algoritmos de grafos podem ser resolvidos eficientemente em grafos de largura de caminho delimitados, usando programação dinâmica em uma decomposição em caminho do grafo. Decomposição em caminho pode também ser usada para medir complexidade de espaço de algoritmos de programação dinâmica em grafos de . (pt)
- У теорії графів шляхова декомпозиція графа G — це, неформально, подання графа G у вигляді «потовщеного» шляху, а шляхова ширина графа G — це число, що вимірює, наскільки граф G був потовщений. Формальніше, шляхова декомпозиція — це послідовності вершин підмножини графа G, такі, що кінцеві вершини кожного ребра з'являються в одній з підмножин і кожна вершина належить (хоча б) одній множині, а шляхова ширина на одиницю менша від розміру найбільшої множини в цій декомпозиції. Шляхова ширина відома також як інтервальна товщина (на одиницю менше від розміру найбільшої кліки інтервального суперграфа графа G), величина вершинного розділення, чи вершинно-пошукове число. Шляхова ширина і шляхова декомпозиція є тісною аналогією з деревною шириною і деревною декомпозицією. Вони відіграють ключову роль у теорії мінорів графа — сімейства графів, які замкнуті відносно мінорів графа і не включають усі дерева, можна схарактеризувати як такі, що мають обмежену шляхову ширину, і «вихори», що виникають у загальній структурній теорії сімейств графів, замкнутих за мінором, мають обмежену шляхову ширину. Шляхова ширина і графи з обмеженою шляховою шириною застосовуються в розробці НВІС, візуалізації графів та комп'ютерній лінгвістиці. Задача знаходження шляхової ширини довільних графів є NP-складною. Більше того, NP-складною є навіть задача апроксимації шляхової ширини точно. Однак ця задача є фіксовано-параметрично розв'язною — перевірку, чи має граф шляхову ширину k, можна здійснити за час, який лінійно залежить від розміру графа, але суперекспоненціально від k. Крім того, для деяких особливих класів графів, таких як дерева, шляхову ширину можна обчислити за поліноміальний час, не залежний від k. Багато задач теорії графів можна ефективно розв'язати на графах з обмеженою шляховою шириною за допомогою динамічного програмування на шляховій декомпозиції графа. Деревну декомпозицію можна також використовувати для оцінювання ємнісної складності алгоритмів динамічного програмування на графах з обмеженою деревною шириною. (uk)
|
| rdfs:comment
|
- Die Pfadweite oder Wegweite ist ein Begriff aus der Graphentheorie. Sie sagt aus, wie „pfad-ähnlich“ ein Graph ist. Da viele Algorithmen auf Pfaden (oder Pfadzerlegungen) effizient laufen, die dies auf allgemeinen Graphen nicht tun, ist es interessant, die Pfadweite zu kennen. Ein verwandter Begriff ist die Baumweite. (de)
- In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G 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 in an interval supergraph of G), vertex separation number, or node searching number. (en)
- Em teoria dos grafos, uma decomposição em caminho de um grafo G é, informalmente, uma representação de G como um caminho "alargado", e o pathwidth ou largura de caminho de G é um número que mede quanto o caminho foi ampliado em largura a partir de G. Mais formalmente, decomposição em caminho é uma sequência de subconjuntos de vértices de G em que os nós extremos de cada aresta apareçam em um dos subconjuntos e que cada vértice apareça em uma subsequência adjacente dos subconjuntos, e a largura de caminho é um a menos que o tamanho do maior conjunto em dada decomposição. Largura de caminho é também conhecida como largura de intervalo (um a menos que o tamanho do clique máximo em um de de G), número de separação de vértice, ou número de busca de nós. (pt)
- В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён. Более формально, путевая декомпозиция — это последовательности вершин подмножества графа G, такие, что конечные вершины каждого ребра появляются в одном из подмножеств и каждая вершина принадлежит (хотя бы) одному из множеств, а путевая ширина на единицу меньше размера наибольшего множества в такой декомпозиции.Путевая ширина известна также как интервальная толщина (на единицу меньше размера наибольшей клики интервального суперграфа графа G), величина вершинного разделения или вершинно-поисковое число. (ru)
- У теорії графів шляхова декомпозиція графа G — це, неформально, подання графа G у вигляді «потовщеного» шляху, а шляхова ширина графа G — це число, що вимірює, наскільки граф G був потовщений. Формальніше, шляхова декомпозиція — це послідовності вершин підмножини графа G, такі, що кінцеві вершини кожного ребра з'являються в одній з підмножин і кожна вершина належить (хоча б) одній множині, а шляхова ширина на одиницю менша від розміру найбільшої множини в цій декомпозиції. Шляхова ширина відома також як інтервальна товщина (на одиницю менше від розміру найбільшої кліки інтервального суперграфа графа G), величина вершинного розділення, чи вершинно-пошукове число. (uk)
|
