{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T06:40:49Z","timestamp":1698043249303},"reference-count":8,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5550,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1991,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The complexity of many combinatorial algorithms is directly related to the number of upsets (filters) in an underlying partial order or, equivalently, to the number of downsets (ideals) that are the complements of upsets. In this paper, we investigate the expected number of upsets in randomly generated two\u2010dimensional partial orders and present a number of new results, together with simple combinatorial proofs of some known results. As an application of our results, we show that some well\u2010known algorithms for precedence constrained scheduling have nonpolynomial expected time and storage complexity.<\/jats:p>","DOI":"10.1002\/net.3230210502","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T11:17:51Z","timestamp":1178968671000},"page":"487-503","source":"Crossref","is-referenced-by-count":0,"title":["Average properties of two\u2010dimensional partial orders"],"prefix":"10.1002","volume":"21","author":[{"given":"J. B.","family":"Sidney","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. J.","family":"Sidney","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Warburton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller W.","year":"1970"},{"key":"e_1_2_1_3_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010completeness","author":"Garey M. A.","year":"1979"},{"key":"e_1_2_1_4_2","volume-title":"Combinatorial Optimization: An Annotated Bibliography","author":"Karp R. M.","year":"1985"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.2307\/2042390"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.3.444"},{"key":"e_1_2_1_7_2","unstructured":"J.Sidney S.Sidney andA.Warburton The expected number of ideals in partial orders of dimension 2. Working paper Faculty of Administration University of Ottawa Ottawa Ontario Canada (1987)."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.9.2.248"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(86)90071-4"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230210502","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230210502","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T00:02:52Z","timestamp":1698019372000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230210502"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,8]]},"references-count":8,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1991,8]]}},"alternative-id":["10.1002\/net.3230210502"],"URL":"https:\/\/doi.org\/10.1002\/net.3230210502","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,8]]}}}