Path decomposition

Path decomposition

In graph theory, a path decomposition of a graph G is a tree decomposition (X,T) where T is a path. The path width of G is the least integer k such that G has a path decomposition of width k.

Computing the path width of a graph is NP-hard.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Decomposition arborescente — Décomposition arborescente En théorie des graphes, la décomposition arborescente (en anglais : tree decomposition) consiste en la décomposition d un graphe en séparateurs connectés dans un arbre. Cette méthode a été proposée par Seymour et… …   Wikipédia en Français

  • Décomposition-arbre — Décomposition arborescente En théorie des graphes, la décomposition arborescente (en anglais : tree decomposition) consiste en la décomposition d un graphe en séparateurs connectés dans un arbre. Cette méthode a été proposée par Seymour et… …   Wikipédia en Français

  • Décomposition Arborescente — En théorie des graphes, la décomposition arborescente (en anglais : tree decomposition) consiste en la décomposition d un graphe en séparateurs connectés dans un arbre. Cette méthode a été proposée par Seymour et Robertson dans le cadre de… …   Wikipédia en Français

  • Décomposition arborescente — En théorie des graphes, la décomposition arborescente (en anglais : tree decomposition) consiste en la décomposition d un graphe en séparateurs connectés dans un arbre. Cette méthode a été proposée par Seymour et Robertson dans le cadre de… …   Wikipédia en Français

  • Decomposition method (constraint satisfaction) — In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a… …   Wikipedia

  • Tree decomposition — A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the… …   Wikipedia

  • Hamiltonian path — This article is about the overall graph theory concept of a Hamiltonian path. For the specific problem of determining whether a Hamiltonian path or cycle exists in a given graph, see Hamiltonian path problem. A Hamiltonian cycle in a dodecahedron …   Wikipedia

  • Littelmann path model — In mathematics, the Littelmann path model is a combinatorial device due to Peter Littelmann for computing multiplicities without overcounting in the representation theory of symmetrisable Kac Moody algebras. Its most important application is to… …   Wikipedia

  • Boustrophedon cell decomposition — The boustrophedon cell decomposition is a method used in artificial intelligence and robotics for configuration space solutions. Like other cellular decomposition methods, this method transforms the configuration space into cell regions that can… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”