| dbo:abstract
|
- Die Cliquenweite ist ein Begriff aus der Graphentheorie und ordnet jedem ungerichteten Graphen eine natürliche Zahl zu. Sie ist daher ein . Mit Hilfe eines k-Ausdrucks (s. u.) lassen sich viele NP-vollständige Probleme wie zum Beispiel HAMILTONKREIS oder CLIQUE und das damit eng verwandte UNABHÄNGIGE MENGE in Zeit lösen, was für konstante eine lineare Laufzeit ist. Da jedoch nicht bekannt ist, ob ein k-Ausdruck hinreichend schnell berechnet werden kann, ist es zur Zeit unklar, ob man hieraus folgern kann, dass diese Probleme auf Graphen mit beschränkter Cliquenweite effizient zu lösen sind. (de)
- In graph theory, the clique-width of a graph G is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs.It is defined as the minimum number of labels needed to construct G by means of the following 4 operations : 1.
* Creation of a new vertex v with label i (denoted by i(v)) 2.
* Disjoint union of two labeled graphs G and H (denoted by ) 3.
* Joining by an edge every vertex labeled i to every vertex labeled j (denoted by η(i,j)), where i ≠ j 4.
* Renaming label i to label j (denoted by ρ(i,j)) Graphs of bounded clique-width include the cographs and distance-hereditary graphs. Although it is NP-hard to compute the clique-width when it is unbounded, and unknown whether it can be computed in polynomial time when it is bounded, efficient approximation algorithms for clique-width are known.Based on these algorithms and on Courcelle's theorem, many graph optimization problems that are NP-hard for arbitrary graphs can be solved or approximated quickly on the graphs of bounded clique-width. The construction sequences underlying the concept of clique-width were formulated by Courcelle, Engelfriet, and Rozenberg in 1990 and by . The name "clique-width" was used for a different concept by . By 1993, the term already had its present meaning. (en)
- En théorie des graphes, la largeur de clique d'un graphe est l'un des paramètres qui décrit la complexité structurelle du graphe ; il est étroitement lié à largeur arborescente, mais contrairement à celle-ci, elle peut être bornée même pour des graphes denses . (fr)
- В теории графов кликовая ширина графа — это параметр, который описывает структурную сложность графа. Параметр тесно связан с древесной шириной, но, в отличие от древесной ширины, кликовая ширина может быть ограничена даже для плотных графов.Кликовая ширина определяется как минимальное число меток, необходимых для построения с помощью следующих 4 операций 1.
* Создание новой вершины v с меткой i (операция i(v)) 2.
* Несвязное объединение двух размеченных графов G и H (операция ) 3.
* Соединение ребром каждой вершины с меткой i с каждой вершиной с меткой j (операция η(i, j)), где 4.
* Переименование метки i в j (операция ρ(i,j)) В графы с ограниченной кликовой шириной входят кографы и дистанционно-наследуемые графы. Хотя вычисление кликовой ширины является NP-трудной задачей, при условии, что верхняя граница не известна, и неизвестно, можно ли её вычислить за полиномиальное время, когда верхняя граница известна, эффективные аппроксимационные алгоритмы вычисления кликовой ширины известны.Опираясь на эти алгоритмы и теорему Курселя, многие оптимизационные задачи на графах, NP-трудные для произвольных графов, могут быть решены или аппроксимированы быстро для графов с ограниченной кликовой шириной. Последовательности построения, на которые опирается понятие кликовой ширины, сформулировали Курсель, Энгельфрид и Розенберг в 1990 и Ванке. Название «кликовая ширина» использовала для другой концепции Хлебикова. С 1993 термин стал употребляться в современном значении. (ru)
- В теорії графів клікова ширина графа — це параметр, який описує структурну складність графа. Параметр тісно пов'язаний з деревною шириною, але, на відміну від деревної ширини, клікова ширина може бути обмеженою навіть для щільних графів. Клікова ширина визначається як мінімальна кількість міток, необхідних для побудови за допомогою таких 4 операцій: 1.
* Створення нової вершини v з міткою i (операція i(v)) 2.
* Незв'язне об'єднання двох розмічених графів G і H (операція ) 3.
* З'єднання ребром кожної вершини з міткою i з кожною вершиною з міткою j (операція η(i, j)), де 4.
* Перейменування мітки i на j (операція ρ(i,j)) До графів з обмеженою кліковою шириною належать кографи і дистанційно-успадковувані графи. Хоча обчислення клікової ширини є NP-складною задачею, за умови, що верхня межа не відома, і невідомо, чи можна її обчислити за поліноміальний час, коли верхня межа відома, ефективні апроксимаційні алгоритми обчислення клікової ширини відомі. Спираючись на ці алгоритми і теорему Курселя, багато оптимізаційних задач на графах, NP-складних для довільних графів, можна розв'язати або швидко апроксимувати для графів з обмеженою кліковою шириною. Послідовності побудови, на які спирається поняття клікової ширини, сформулювали Курсель, Енгельфрід і Розенберг у 1990 і Ванке. Назву «клікова ширина» використала для іншої концепції Хлєбікова. Від 1993 термін став уживатися в сучасному значенні. (uk)
|
| rdfs:comment
|
- Die Cliquenweite ist ein Begriff aus der Graphentheorie und ordnet jedem ungerichteten Graphen eine natürliche Zahl zu. Sie ist daher ein . Mit Hilfe eines k-Ausdrucks (s. u.) lassen sich viele NP-vollständige Probleme wie zum Beispiel HAMILTONKREIS oder CLIQUE und das damit eng verwandte UNABHÄNGIGE MENGE in Zeit lösen, was für konstante eine lineare Laufzeit ist. Da jedoch nicht bekannt ist, ob ein k-Ausdruck hinreichend schnell berechnet werden kann, ist es zur Zeit unklar, ob man hieraus folgern kann, dass diese Probleme auf Graphen mit beschränkter Cliquenweite effizient zu lösen sind. (de)
- En théorie des graphes, la largeur de clique d'un graphe est l'un des paramètres qui décrit la complexité structurelle du graphe ; il est étroitement lié à largeur arborescente, mais contrairement à celle-ci, elle peut être bornée même pour des graphes denses . (fr)
- In graph theory, the clique-width of a graph G is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs.It is defined as the minimum number of labels needed to construct G by means of the following 4 operations : The construction sequences underlying the concept of clique-width were formulated by Courcelle, Engelfriet, and Rozenberg in 1990 and by . The name "clique-width" was used for a different concept by . By 1993, the term already had its present meaning. (en)
- В теории графов кликовая ширина графа — это параметр, который описывает структурную сложность графа. Параметр тесно связан с древесной шириной, но, в отличие от древесной ширины, кликовая ширина может быть ограничена даже для плотных графов.Кликовая ширина определяется как минимальное число меток, необходимых для построения с помощью следующих 4 операций (ru)
- В теорії графів клікова ширина графа — це параметр, який описує структурну складність графа. Параметр тісно пов'язаний з деревною шириною, але, на відміну від деревної ширини, клікова ширина може бути обмеженою навіть для щільних графів. Клікова ширина визначається як мінімальна кількість міток, необхідних для побудови за допомогою таких 4 операцій: Послідовності побудови, на які спирається поняття клікової ширини, сформулювали Курсель, Енгельфрід і Розенберг у 1990 і Ванке. Назву «клікова ширина» використала для іншої концепції Хлєбікова. Від 1993 термін став уживатися в сучасному значенні. (uk)
|
