Abstract
We consider a planning problem that generalizes Alcuin’s river crossing problem (also known as: The wolf, goat, and cabbage puzzle) to scenarios with arbitrary conflict graphs. We derive a variety of combinatorial, structural, algorithmical, and complexity theoretical results around this problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ascher, M.: A river-crossing problem in cross-cultural perspective. Mathematics Magazine 63, 26–29 (1990)
Bahls, P.: The wolf, the goat, and the cabbage: A modern twist on a classical problem. University of North Carolina, Asheville (unpublished manuscript, 2005)
Biggs, N.L.: The roots of combinatorics. Historia Mathematica 6, 109–136 (1979)
Borndörfer, R., Grötschel, M., Löbel, A.: Alcuin’s transportation problems and integer programming. In: Charlemagne and his heritage. 1200 years of civilization and science in Europe, Brepols, Turnhout, vol. 2, pp. 379–409 (1998)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric algorithms and combinatorial optimization. Springer, New York (1988)
Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2 − ε. Journal of Computer and System Sciences 74, 335–349 (2008)
Lampis, M., Mitsou, V.: The ferry cover problem. In: Crescenzi, P., Prencipe, G., Pucci, G. (eds.) FUN 2007. LNCS, vol. 4475, pp. 227–239. Springer, Heidelberg (2007)
Lovász, L., Plummer, M.D.: Matching Theory. Annals of Discrete Mathematics, vol. 29. North-Holland, Amsterdam (1986)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, New York (2006)
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)
Prisner, E.: Generalizing the wolf-goat-cabbage problem. Electronic Notes in Discrete Mathematics 27, 83 (2006)
Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory, Series B 80, 346–355 (2000)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Csorba, P., Hurkens, C.A.J., Woeginger, G.J. (2008). The Alcuin Number of a Graph. In: Halperin, D., Mehlhorn, K. (eds) Algorithms - ESA 2008. ESA 2008. Lecture Notes in Computer Science, vol 5193. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87744-8_27
Download citation
DOI: https://doi.org/10.1007/978-3-540-87744-8_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87743-1
Online ISBN: 978-3-540-87744-8
eBook Packages: Computer ScienceComputer Science (R0)