Jeff121 Posted October 16, 2016 Share Posted October 16, 2016 (edited) Considering the problem of transporting n items across a river using a boat that can carry k items, where some pairs of items cannot be left together unsupervised. Let G be the simple graph whose vertices correspond to items, and whose edges join pairs of items that need supervision. How do I show that the minimum size of a boat k for which a solution exists is either Vc(G) or Vc(G)+1, where Vc(G) is the size of a minimum vertex cover of G. Edited October 16, 2016 by Jeff121 Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now