Name
Abstract | ||
|---|---|---|
Three men, each with a sister, must cross a river using a boat which can carry only two people, so that a woman whose brother is not present is never left in the company of another man. This is a very famous problem appeared in Latin book "Problems to Sharpen the Young," one of the earliest collections on recreational mathematics. This paper considers a generalization of such "River-Crossing Problems." It shows that the problem is NP-hard if the boat size is three, and a large class of sub-problems can be solved in polynomial time if the boat size is two. It's also conjectured that determining whether a river crossing problem has a solution without bounding the number of transportations, can be solved in polynomial time even when the size of the boat is large. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-30347-0_24 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
recreational mathematics,large class,river-crossing problems,latin book,boat size,generalized river,earliest collection,polynomial time,famous problem | Discrete mathematics,Computer science,Algorithm,Sister,Recreational mathematics,Brother,Vertex cover,Time complexity,Bounding overwatch | Conference |
Citations | PageRank | References |
1 | 0.41 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiro Ito | 1 | 290 | 39.95 |
| Stefan Langerman | 2 | 831 | 101.66 |
| Yuichi Yoshida | 3 | 469 | 44.88 |