Path decomposition

From Wikipedia, the free encyclopedia

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.

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../p/a/t/Path_decomposition.html"