scientific article; zbMATH DE number 3956440
From MaRDI portal
Publication:3725545
zbMATH Open0594.68042MaRDI QIDQ3725545FDOQ3725545
Authors: Burkhard Monien, I. H. Sudborough 
Publication date: 1986
Title of this publication is not available (Why is that?)
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
Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cited In (14)
- Min Cut is NP-complete for edge weighted trees
- ``Global graph problems tend to be intractable
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Bounds on mincut for Cayley graphs over Abelian groups
- Efficient parallel algorithms for some tree layout problems
- Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
- NP-completeness of the Planar Separator Problems
- Parallel algorithms for the minimum cut and the minimum length tree layout problems
- On the complexity of isoperimetric problems on trees
- On the complexity of loading shallow neural networks
- A variation on the min cut linear arrangement problem
- Tree-width, path-width, and cutwidth
- Computing the cutwidth of bipartite permutation graphs in linear time
- Minimal cutwidth linear arrangements of abelian Cayley graphs
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)
