An assignment problem for the vertices of a cycle

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic


Let Cn denote a cycle on n points. For each of its points P a nonnegative integer mp is given. To each point P a subset Mp of {0, 1, ... , N -1} of cardinality mp has to be assigned with the property that neighboring points will have mutually disjoint associated sets. An expression will be derived for the smallest value of N for which such an assigment is possible. The assignment itself will also be given explicitly.
Original languageEnglish
Title of host publicationBeauty is our business : a birthday salute to Edsger W. Dijkstra
EditorsW.H.J. Feijen, A.J.M. Gasteren, van, D. Gries, J. Misra
Place of PublicationBerlin
ISBN (Print)0-387-97299-4
Publication statusPublished - 1990

Publication series

NameTexts and monographs in computer science
ISSN (Print)0172-603X


Dive into the research topics of 'An assignment problem for the vertices of a cycle'. Together they form a unique fingerprint.

Cite this