11 reputation
2
bio website
location
age
visits member for 2 years, 7 months
seen Mar 13 '12 at 4:22

Mar
12
awarded  Student
Mar
12
comment NP-Completeness of Certain Bounded Degree Graphs
Right, I am just not sure how to generalize from a graph of max degree 1.
Mar
11
asked 2-Player Game PSpace-Completeness
Mar
10
comment NP-Completeness of Certain Bounded Degree Graphs
Well if the max degree is 1, then the clique can have at most size 2. That can be verified in P time by just crawling through the vertices, I am not sure about how to generalize that into a reduction.
Mar
10
awarded  Editor
Mar
10
revised NP-Completeness of Certain Bounded Degree Graphs
added 263 characters in body
Mar
10
asked NP-Completeness of Certain Bounded Degree Graphs