Toggle navigation
PDFSEARCH.IO
Document Search Engine - browse more than 18 million documents
Sign up
Sign in
Back to Results
First Page
Meta Content
View Document Preview and Link
CS109B Notes for LectureNP-Complete Problems We have met some problems that have \easy" solutions; they have algorithms that run in time that is polynomial in the size of the graph, the parameter m. Examples:
Add to Reading List
Document Date: 2008-09-19 00:58:50
Open Document
File Size: 56,61 KB
Share Result on Facebook
SocialTag
NP-complete problems
Graph coloring
Independent set
NP-complete
Clique
Vertex cover
NP
Clique cover problem
Domatic number
Theoretical computer science
CS109B Notes for LectureNP-Complete Problems We have met some problems that have \easy" solutions; they have algorithms that run in time that is polynomial in the size of the graph, the parameter m. Examples: