{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T23:05:24Z","timestamp":1779836724156,"version":"3.53.1"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2001,9,4]],"date-time":"2001-09-04T00:00:00Z","timestamp":999561600000},"content-version":"unspecified","delay-in-days":65,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2001,7]]},"abstract":"<jats:p>Here are two puzzles for you to solve. First, consider the binary tree in figure 1. \nTake a pencil (I am assuming that this is your personal copy of JFP!) and mark \nsome of the nodes in such a way that the sum of the values of marked nodes is \nas large as possible. The catch is that you cannot mark all the nodes: if you mark \na node, then you are not allowed to mark its parent. Equivalently, no two marked \nnodes can be contiguous in the tree.<\/jats:p>\n                  <jats:p>\n                    The second puzzle is similar though both the datatype and constraint are different. \nConsider the rose tree of figure 2 (a rose tree is a tree with arbitrary branching \nstructure). Mark some of the nodes so that all marked nodes are now\n                    <jats:italic>contiguous<\/jats:italic>\n                    in \nthe tree. For example, if you mark the root value 4 and the leaf value 1, then you \nmust also mark the values 5 and \u22123 along the path from 4 to 1. Again the idea is \nto maximise the sum of the marked nodes. Of course, if all values were nonnegative, \nthe best solution would be to mark all nodes. But they aren't and the maximum \nsum is obtained only by a judicious choice of marking. Answers to both puzzles are \ngiven at the end of the paper.\n                  <\/jats:p>\n                  <jats:p>The Maximum Marking Problem (MMP) is the problem of marking the entries \nof some given data structure in such a way that a given constraint is satisfied and \nthe sum of the values associated with marked entries is as large as possible. By the \nend of this pearl, you will be convinced that there is a linear-time solution for both \nthe puzzles described above.<\/jats:p>","DOI":"10.1017\/s0956796801004038","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T09:16:52Z","timestamp":1027761412000},"page":"411-424","source":"Crossref","is-referenced-by-count":8,"title":["Maximum marking problems"],"prefix":"10.1017","volume":"11","author":[{"given":"RICHARD S.","family":"BIRD","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2001,9,4]]},"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796801004038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T22:35:36Z","timestamp":1779834936000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796801004038\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,7]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2001,7]]}},"alternative-id":["S0956796801004038"],"URL":"https:\/\/doi.org\/10.1017\/s0956796801004038","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,7]]}}}