Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q7144893> ?p ?o }
- Q7144893 subject Q6465283.
- Q7144893 subject Q8498914.
- Q7144893 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.".
- Q7144893 thumbnail Pathwidth.JPG?width=300.
- Q7144893 wikiPageExternalLink dm030404.pdf.
- Q7144893 wikiPageExternalLink BGT.pdf.
- Q7144893 wikiPageExternalLink lamc6dynulxv7a8n.
- Q7144893 wikiPageExternalLink DMW-GD02.pdf.
- Q7144893 wikiPageExternalLink SOCS-02-8.pdf.
- Q7144893 wikiPageExternalLink full.pdf.
- Q7144893 wikiPageExternalLink j31.pdf.
- Q7144893 wikiPageExternalLink miller1956.
- Q7144893 wikiPageWikiLink Q1101814.
- Q7144893 wikiPageWikiLink Q1137554.
- Q7144893 wikiPageWikiLink Q1155722.
- Q7144893 wikiPageWikiLink Q1187620.
- Q7144893 wikiPageWikiLink Q1195339.
- Q7144893 wikiPageWikiLink Q127748.
- Q7144893 wikiPageWikiLink Q129239.
- Q7144893 wikiPageWikiLink Q131476.
- Q7144893 wikiPageWikiLink Q13222616.
- Q7144893 wikiPageWikiLink Q1322892.
- Q7144893 wikiPageWikiLink Q1343660.
- Q7144893 wikiPageWikiLink Q1374495.
- Q7144893 wikiPageWikiLink Q1378376.
- Q7144893 wikiPageWikiLink Q1422857.
- Q7144893 wikiPageWikiLink Q1475294.
- Q7144893 wikiPageWikiLink Q15284723.
- Q7144893 wikiPageWikiLink Q1570441.
- Q7144893 wikiPageWikiLink Q15759553.
- Q7144893 wikiPageWikiLink Q166507.
- Q7144893 wikiPageWikiLink Q173183.
- Q7144893 wikiPageWikiLink Q173431.
- Q7144893 wikiPageWikiLink Q174733.
- Q7144893 wikiPageWikiLink Q182557.
- Q7144893 wikiPageWikiLink Q2112217.
- Q7144893 wikiPageWikiLink Q211496.
- Q7144893 wikiPageWikiLink Q215206.
- Q7144893 wikiPageWikiLink Q221653.
- Q7144893 wikiPageWikiLink Q2294516.
- Q7144893 wikiPageWikiLink Q2393193.
- Q7144893 wikiPageWikiLink Q266775.
- Q7144893 wikiPageWikiLink Q272735.
- Q7144893 wikiPageWikiLink Q2835897.
- Q7144893 wikiPageWikiLink Q2913731.
- Q7144893 wikiPageWikiLink Q2915204.
- Q7144893 wikiPageWikiLink Q30642.
- Q7144893 wikiPageWikiLink Q3115604.
- Q7144893 wikiPageWikiLink Q3186905.
- Q7144893 wikiPageWikiLink Q3498041.
- Q7144893 wikiPageWikiLink Q3527155.
- Q7144893 wikiPageWikiLink Q369377.
- Q7144893 wikiPageWikiLink Q380172.
- Q7144893 wikiPageWikiLink Q380679.
- Q7144893 wikiPageWikiLink Q383444.
- Q7144893 wikiPageWikiLink Q3893853.
- Q7144893 wikiPageWikiLink Q45715.
- Q7144893 wikiPageWikiLink Q462095.
- Q7144893 wikiPageWikiLink Q47506.
- Q7144893 wikiPageWikiLink Q4951712.
- Q7144893 wikiPageWikiLink Q504843.
- Q7144893 wikiPageWikiLink Q5051951.
- Q7144893 wikiPageWikiLink Q5067368.
- Q7144893 wikiPageWikiLink Q5121450.
- Q7144893 wikiPageWikiLink Q5121634.
- Q7144893 wikiPageWikiLink Q5134410.
- Q7144893 wikiPageWikiLink Q5141281.
- Q7144893 wikiPageWikiLink Q5155607.
- Q7144893 wikiPageWikiLink Q5251771.
- Q7144893 wikiPageWikiLink Q5282038.
- Q7144893 wikiPageWikiLink Q5282847.
- Q7144893 wikiPageWikiLink Q5413264.
- Q7144893 wikiPageWikiLink Q5467387.
- Q7144893 wikiPageWikiLink Q547823.
- Q7144893 wikiPageWikiLink Q5597073.
- Q7144893 wikiPageWikiLink Q5597085.
- Q7144893 wikiPageWikiLink Q5597098.
- Q7144893 wikiPageWikiLink Q5693708.
- Q7144893 wikiPageWikiLink Q573901.
- Q7144893 wikiPageWikiLink Q5808319.
- Q7144893 wikiPageWikiLink Q6030974.
- Q7144893 wikiPageWikiLink Q6049376.
- Q7144893 wikiPageWikiLink Q6051350.
- Q7144893 wikiPageWikiLink Q6053776.
- Q7144893 wikiPageWikiLink Q6053791.
- Q7144893 wikiPageWikiLink Q6057290.
- Q7144893 wikiPageWikiLink Q621751.
- Q7144893 wikiPageWikiLink Q6295265.
- Q7144893 wikiPageWikiLink Q6465283.
- Q7144893 wikiPageWikiLink Q6553253.
- Q7144893 wikiPageWikiLink Q7169369.
- Q7144893 wikiPageWikiLink Q7200963.
- Q7144893 wikiPageWikiLink Q7256370.
- Q7144893 wikiPageWikiLink Q7261573.
- Q7144893 wikiPageWikiLink Q7390256.
- Q7144893 wikiPageWikiLink Q7390263.
- Q7144893 wikiPageWikiLink Q739462.
- Q7144893 wikiPageWikiLink Q7395156.
- Q7144893 wikiPageWikiLink Q7454787.
- Q7144893 wikiPageWikiLink Q753127.