Maximizing edge-ratio is NP-complete.
Steven D. NoblePierre HansenNenad MladenovicPublished in: Discret. Appl. Math. (2011)
Keyphrases
- np complete
- randomly generated
- edge information
- np hard
- constraint satisfaction problems
- edge detection
- satisfiability problem
- np complete problems
- computational complexity
- pspace complete
- phase transition
- polynomial time complexity
- bounded treewidth
- conjunctive queries
- edge detector
- polynomially solvable
- conp complete
- disjoint paths
- image processing
- data complexity
- undirected graph
- weighted graph
- standard deviation
- branch and bound algorithm
- bayesian networks