Pathwidth (original) (raw)
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.
| Property | Value |
|---|---|
| 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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Pathwidth.jpg?width=300 |
| dbo:wikiPageExternalLink | http://lca.ceid.upatras.gr/~kirousis/publications/j31.pdf http://igitur-archive.library.uu.nl/dissertations/01847381/full.pdf http://www.ii.uib.no/~telle/bib/BGT.pdf http://www.emis.de/journals/DMTCS/volumes/abstracts/pdfpapers/dm030404.pdf https://hal.inria.fr/inria-00070220/file/RR-5804.pdf https://hal.inria.fr/inria-00587819/file/paper-noformat.pdf http://cgm.cs.mcgill.ca/~msuder/schools/mcgill/research/trees/SOCS-02-8.pdf http://cg.scs.carleton.ca/~vida/pubs/papers/DMW-GD02.pdf https://web.archive.org/web/20030503103911/http:/cgm.cs.mcgill.ca/~msuder/schools/mcgill/research/trees/SOCS-02-8.pdf https://web.archive.org/web/20110721084127/http:/lca.ceid.upatras.gr/~kirousis/publications/j31.pdf https://web.archive.org/web/20110724173550/http:/igitur-archive.library.uu.nl/dissertations/01847381/full.pdf http://www.springerlink.com/content/lamc6dynulxv7a8n/ http://www.musanim.com/miller1956/ |
| dbo:wikiPageID | 5133142 (xsd:integer) |
| dbo:wikiPageLength | 66672 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1097177469 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Natural_language_processing dbr:Topological_ordering dbr:Degeneracy_(graph_theory) dbr:Algorithmica dbc:Graph_minor_theory dbr:Path_graph dbr:Cubic_graph dbr:Utrecht_University dbr:VLSI dbr:Degree_(graph_theory) dbr:Induced_subgraph dbr:Information_Processing_Letters dbr:Information_and_Computation dbr:International_Journal_of_Computational_Geometry_and_Applications dbr:Interval_order dbr:Register_allocation dbr:Psychological_Review dbr:Robertson–Seymour_theorem dbr:Perfect_binary_tree dbc:Graph_invariants dbr:Compiler dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Crossing_number_(graph_theory) dbr:Maximum_cut dbr:Genus_(mathematics) dbr:Order_(journal) dbr:Strahler_number dbr:Pursuit–evasion dbr:Clique-sum dbr:Clique-width dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Graph_bandwidth dbr:Graph_coloring dbr:Graph_minor dbr:Graph_structure_theorem dbr:Boxicity dbr:NP-complete dbr:NP-hard dbr:Control_flow dbr:SIAM_Journal_on_Computing dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Line_graph dbr:Linear_order dbr:Lower_bound dbr:Combinatorics,_Probability_and_Computing dbr:Comparability_graph dbr:Complement_graph dbr:Computational_linguistics dbr:Halin_graph dbr:Perfect_graph dbr:Planar_separator_theorem dbr:Programmable_logic_array dbr:Theoretical_Computer_Science_(journal) dbr:Acta_Informatica dbr:Tree_(graph_theory) dbr:Tree_decomposition dbr:Treewidth dbr:Lecture_Notes_in_Computer_Science dbr:Line_graph_of_a_hypergraph dbr:Cutwidth dbr:Dual_graph dbr:Dynamic_programming dbr:Forbidden_graph_characterization dbr:Outerplanar_graph dbr:Discrete_Applied_Mathematics dbr:Discrete_Mathematics_(journal) dbr:Graph_drawing dbr:Graph_embedding dbr:Graph_theory dbr:Graphs_and_Combinatorics dbr:Journal_of_Combinatorial_Theory dbr:Journal_of_Graph_Theory dbr:Tree-depth dbr:Intersection_graph dbr:Interval_graph dbr:Hypergraph dbr:Fixed-parameter_tractable dbr:Chordal_graph dbr:Bipartite_graph dbr:Cograph dbr:High-level_programming_language dbr:Directed_acyclic_graph dbr:Distance-hereditary_graph dbr:CMOS dbr:Planar_graph dbr:Split_graph dbr:Circle_graph dbr:Circular-arc_graph dbr:Approximation_ratio dbr:Caterpillar_tree dbr:Maximal_element dbr:Vertex_(graph_theory) dbr:Exponential_time dbr:Series–parallel_graph dbr:Maximal_clique dbr:Maximum_clique dbr:Permutation_graph dbr:Subset dbr:Wagner's_theorem dbr:Space_complexity dbr:Boolean_logic dbr:Minimum_dominating_set dbr:File:Caterpillar_tree.svg dbr:File:Interval_graph.svg dbr:File:Pathwidth-1_obstructions.svg dbr:File:Pathwidth.JPG |
| dbp:author1Link | Neil Robertson (en) |
| dbp:author2Link | Paul Seymour (en) |
| dbp:bot | medic (en) |
| dbp:date | May 2020 (en) |
| dbp:first | Neil (en) Paul (en) |
| dbp:last | Robertson (en) Seymour (en) |
| dbp:wikiPageUsesTemplate | dbt:Cbignore dbt:Citation dbt:Cite_journal dbt:Dead_link dbt:Frac dbt:Harvtxt dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Sqrt dbt:Sub dbt:Sup dbt:Harvp dbt:Abs dbt:Harvs dbt:Unsolved |
| dbp:year | 1983 (xsd:integer) |
| dcterms:subject | dbc:Graph_minor_theory dbc:Graph_invariants |
| gold:hypernym | dbr:Number |
| rdf:type | yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants |
| 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) |
| rdfs:label | Pfadweite (de) Pathwidth (en) Largura de Caminho (pt) Путевая ширина (ru) Шляхова ширина графа (uk) |
| owl:sameAs | freebase:Pathwidth yago-res:Pathwidth wikidata:Pathwidth dbpedia-de:Pathwidth dbpedia-fa:Pathwidth dbpedia-pt:Pathwidth dbpedia-ru:Pathwidth dbpedia-uk:Pathwidth https://global.dbpedia.org/id/4tAWH |
| prov:wasDerivedFrom | wikipedia-en:Pathwidth?oldid=1097177469&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Interval_graph.svg wiki-commons:Special:FilePath/Caterpillar_tree.svg wiki-commons:Special:FilePath/Pathwidth-1_obstructions.svg wiki-commons:Special:FilePath/Pathwidth.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Pathwidth |
| is dbo:wikiPageDisambiguates of | dbr:Width_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Path_Decomposition dbr:Path-width dbr:Path_decomposition |
| is dbo:wikiPageWikiLink of | dbr:Degeneracy_(graph_theory) dbr:Cubic_graph dbr:Indifference_graph dbr:Robertson–Seymour_theorem dbr:Universal_point_set dbr:Strahler_number dbr:Pursuit–evasion dbr:Clique-sum dbr:Glossary_of_graph_theory dbr:Graph_bandwidth dbr:Graph_minor dbr:Graph_structure_theorem dbr:Apex_graph dbr:Chordal_completion dbr:Tree_decomposition dbr:Treewidth dbr:GNRS_conjecture dbr:Layered_graph_drawing dbr:Cutwidth dbr:List_of_NP-complete_problems dbr:Tree-depth dbr:Interval_graph dbr:Path_Decomposition dbr:Width_(disambiguation) dbr:Caterpillar_tree dbr:List_of_unsolved_problems_in_mathematics dbr:Permutation_graph dbr:Unknotting_problem dbr:S2S_(mathematics) dbr:Path-width dbr:Path_decomposition |
| is foaf:primaryTopic of | wikipedia-en:Pathwidth |
