pathwidth_computation (488B)
1 # Pathwidth computation 2 3 The [computational_problem] of computing the [pathwidth] of an input [graph] 4 5 https://en.wikipedia.org/wiki/Pathwidth#Special_classes_of_graphs 6 - Is [NP_complete] even on [bounded_degree] [planar_graphs] 7 - Can be computed in [linear_time] for [trees] and [forests] 8 - Can be computed in [polynomial_time] for [treelike] [graphs] 9 - Is [NP_complete] on [weighted_trees], cf [mihai2009pathwidth] 10 11 - [pathwidth_approximation] 12 13 Up: [computational_problem], [pathwidth]