Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Pathwidth> ?p ?o. }
Showing items 1 to 28 of
28
with 100 items per page.
- Pathwidth abstract "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 isa 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.".
- Pathwidth wikiPageExternalLink DMW-GD02.pdf.
- Pathwidth wikiPageExternalLink SOCS-02-8.pdf.
- Pathwidth wikiPageExternalLink full.pdf.
- Pathwidth wikiPageExternalLink j31.pdf.
- Pathwidth wikiPageExternalLink dm030404.pdf.
- Pathwidth wikiPageExternalLink BGT.pdf.
- Pathwidth wikiPageExternalLink miller1956.
- Pathwidth wikiPageExternalLink lamc6dynulxv7a8n.
- Pathwidth wikiPageID "5133142".
- Pathwidth wikiPageRevisionID "599353513".
- Pathwidth author1Link "Neil Robertson".
- Pathwidth author2Link "Paul Seymour".
- Pathwidth first "Neil".
- Pathwidth first "Paul".
- Pathwidth hasPhotoCollection Pathwidth.
- Pathwidth last "Robertson".
- Pathwidth last "Seymour".
- Pathwidth year "1983".
- Pathwidth subject Category:Graph_invariants.
- Pathwidth subject Category:Graph_minor_theory.
- Pathwidth comment "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.".
- Pathwidth label "Pathwidth".
- Pathwidth sameAs m.0d48b5.
- Pathwidth sameAs Q7144893.
- Pathwidth sameAs Q7144893.
- Pathwidth wasDerivedFrom Pathwidth?oldid=599353513.
- Pathwidth isPrimaryTopicOf Pathwidth.