linear variant
Graph decompositions often end up being trees, but still, some problems remain hard on those decompositions. Restricting the decomposition to be a path (or to be linearized in some other way) gives bigger power to the decomposition and makes some problems tractable.
has this tag |
---|
linear clique-width |
pathwidth |
pathwidth+maxdegree |
linear rank-width |
linear NLC-width |
distance to linear forest |