Min Cut is NP-Complete for Edge Weighted Treees.
Burkhard MonienIvan Hal SudboroughPublished in: Theor. Comput. Sci. (1988)
Keyphrases
- np complete
- min cut
- weighted graph
- graph partitioning
- undirected graph
- np hard
- graph cuts
- shortest path
- energy minimization
- constraint satisfaction problems
- computational complexity
- energy function
- global optimization
- shape prior
- graph model
- graph structure
- image segmentation
- data objects
- information theoretic
- pairwise
- interior point