scientific article; zbMATH DE number 3956440
From MaRDI portal
Publication:3725545
Recommendations
- Min Cut is NP-complete for edge weighted trees
- Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
- On minimum bisection and related cut problems in trees and tree-like graphs
- scientific article; zbMATH DE number 2086925
- Parameterized complexity of weighted multicut in trees
- The tree of cuts and minimal \(k\)-connected graphs
- Parameterized complexity of multicut in weighted trees
- Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
- Minimum Cuts of Simple Graphs in Almost Always Linear Time
- Minimax trees, paths, and cut sets
Cited in
(14)- NP-completeness of the Planar Separator Problems
- On the complexity of isoperimetric problems on trees
- Efficient parallel algorithms for some tree layout problems
- Parallel algorithms for the minimum cut and the minimum length tree layout problems
- Computing the cutwidth of bipartite permutation graphs in linear time
- Minimal cutwidth linear arrangements of abelian Cayley graphs
- Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
- ``Global graph problems tend to be intractable
- On the complexity of loading shallow neural networks
- Bounds on mincut for Cayley graphs over Abelian groups
- Min Cut is NP-complete for edge weighted trees
- Tree-width, path-width, and cutwidth
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- A variation on the min cut linear arrangement problem
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3725545)
