Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Pathwidth> ?p ?o }
- 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 full.pdf.
- Pathwidth wikiPageExternalLink dm030404.pdf.
- Pathwidth wikiPageExternalLink BGT.pdf.
- Pathwidth wikiPageExternalLink lamc6dynulxv7a8n.
- Pathwidth wikiPageExternalLink DMW-GD02.pdf.
- Pathwidth wikiPageExternalLink SOCS-02-8.pdf.
- Pathwidth wikiPageExternalLink j31.pdf.
- Pathwidth wikiPageExternalLink miller1956.
- Pathwidth wikiPageID "5133142".
- Pathwidth wikiPageLength "62574".
- Pathwidth wikiPageOutDegree "154".
- Pathwidth wikiPageRevisionID "680114136".
- Pathwidth wikiPageWikiLink Acta_Informatica.
- Pathwidth wikiPageWikiLink Algorithmica.
- Pathwidth wikiPageWikiLink Approximation_algorithm.
- Pathwidth wikiPageWikiLink Approximation_ratio.
- Pathwidth wikiPageWikiLink Binary_tree.
- Pathwidth wikiPageWikiLink Bipartite_graph.
- Pathwidth wikiPageWikiLink Boolean_algebra.
- Pathwidth wikiPageWikiLink Boolean_logic.
- Pathwidth wikiPageWikiLink Boxicity.
- Pathwidth wikiPageWikiLink CMOS.
- Pathwidth wikiPageWikiLink Category:Graph_invariants.
- Pathwidth wikiPageWikiLink Category:Graph_minor_theory.
- Pathwidth wikiPageWikiLink Caterpillar_tree.
- Pathwidth wikiPageWikiLink Chordal_graph.
- Pathwidth wikiPageWikiLink Circle_graph.
- Pathwidth wikiPageWikiLink Circular-arc_graph.
- Pathwidth wikiPageWikiLink Clique-sum.
- Pathwidth wikiPageWikiLink Clique-width.
- Pathwidth wikiPageWikiLink Clique_(graph_theory).
- Pathwidth wikiPageWikiLink Cograph.
- Pathwidth wikiPageWikiLink Combinatorics,_Probability_and_Computing.
- Pathwidth wikiPageWikiLink Comparability_graph.
- Pathwidth wikiPageWikiLink Compiler.
- Pathwidth wikiPageWikiLink Complement_graph.
- Pathwidth wikiPageWikiLink Complete_bipartite_graph.
- Pathwidth wikiPageWikiLink Complete_graph.
- Pathwidth wikiPageWikiLink Computational_linguistics.
- Pathwidth wikiPageWikiLink Control_flow.
- Pathwidth wikiPageWikiLink Crossing_number_(graph_theory).
- Pathwidth wikiPageWikiLink Cubic_graph.
- Pathwidth wikiPageWikiLink Cutwidth.
- Pathwidth wikiPageWikiLink DSPACE.
- Pathwidth wikiPageWikiLink Degeneracy_(graph_theory).
- Pathwidth wikiPageWikiLink Degree_(graph_theory).
- Pathwidth wikiPageWikiLink Directed_acyclic_graph.
- Pathwidth wikiPageWikiLink Discrete_Mathematics_(journal).
- Pathwidth wikiPageWikiLink Distance-hereditary_graph.
- Pathwidth wikiPageWikiLink Dominating_set.
- Pathwidth wikiPageWikiLink Dual_graph.
- Pathwidth wikiPageWikiLink Dynamic_programming.
- Pathwidth wikiPageWikiLink European_Symposium_on_Algorithms.
- Pathwidth wikiPageWikiLink Exponential_time.
- Pathwidth wikiPageWikiLink Fixed-parameter_tractable.
- Pathwidth wikiPageWikiLink Forbidden_graph_characterization.
- Pathwidth wikiPageWikiLink Genus_(mathematics).
- Pathwidth wikiPageWikiLink Glossary_of_graph_theory.
- Pathwidth wikiPageWikiLink Graph_bandwidth.
- Pathwidth wikiPageWikiLink Graph_coloring.
- Pathwidth wikiPageWikiLink Graph_drawing.
- Pathwidth wikiPageWikiLink Graph_embedding.
- Pathwidth wikiPageWikiLink Graph_minor.
- Pathwidth wikiPageWikiLink Graph_structure_theorem.
- Pathwidth wikiPageWikiLink Graph_theory.
- Pathwidth wikiPageWikiLink Halin_graph.
- Pathwidth wikiPageWikiLink High-level_programming_language.
- Pathwidth wikiPageWikiLink Hypergraph.
- Pathwidth wikiPageWikiLink Induced_subgraph.
- Pathwidth wikiPageWikiLink Information_Processing_Letters.
- Pathwidth wikiPageWikiLink Information_and_Computation.
- Pathwidth wikiPageWikiLink International_Colloquium_on_Automata,_Languages_and_Programming.
- Pathwidth wikiPageWikiLink International_Symposium_on_Circuits_and_Systems.
- Pathwidth wikiPageWikiLink International_Symposium_on_Graph_Drawing.
- Pathwidth wikiPageWikiLink Intersection_graph.
- Pathwidth wikiPageWikiLink Interval_graph.
- Pathwidth wikiPageWikiLink Interval_order.
- Pathwidth wikiPageWikiLink Journal_of_Combinatorial_Theory.
- Pathwidth wikiPageWikiLink Journal_of_Graph_Theory.
- Pathwidth wikiPageWikiLink Lecture_Notes_in_Computer_Science.
- Pathwidth wikiPageWikiLink Line_graph.
- Pathwidth wikiPageWikiLink Line_graph_of_a_hypergraph.
- Pathwidth wikiPageWikiLink Linear_order.
- Pathwidth wikiPageWikiLink Lower_bound.
- Pathwidth wikiPageWikiLink Maximal_clique.
- Pathwidth wikiPageWikiLink Maximal_element.
- Pathwidth wikiPageWikiLink Maximum_clique.
- Pathwidth wikiPageWikiLink Maximum_cut.
- Pathwidth wikiPageWikiLink Minimum_dominating_set.
- Pathwidth wikiPageWikiLink NP-complete.
- Pathwidth wikiPageWikiLink NP-completeness.
- Pathwidth wikiPageWikiLink NP-hard.
- Pathwidth wikiPageWikiLink NP-hardness.
- Pathwidth wikiPageWikiLink Natural_language_processing.
- Pathwidth wikiPageWikiLink Outerplanar_graph.
- Pathwidth wikiPageWikiLink Parameterized_complexity.
- Pathwidth wikiPageWikiLink Path_graph.
- Pathwidth wikiPageWikiLink Perfect_binary_tree.
- Pathwidth wikiPageWikiLink Perfect_graph.