{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T23:54:44Z","timestamp":1778025284372,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642402722","type":"print"},{"value":"9783642402739","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40273-9_12","type":"book-chapter","created":{"date-parts":[[2013,8,9]],"date-time":"2013-08-09T21:20:34Z","timestamp":1376083234000},"page":"164-175","source":"Crossref","is-referenced-by-count":2,"title":["On Generalized Comparison-Based Sorting Problems"],"prefix":"10.1007","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel","family":"Fiorini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0012-365X(81)90197-7","volume":"35","author":"M. Aigner","year":"1981","unstructured":"Aigner, M.: Producing posets. Discrete Math.\u00a035, 1\u201315 (1981)","journal-title":"Discrete Math."},{"key":"12_CR2","unstructured":"Alon, N., Blum, M., Fiat, A., Kannan, S., Naor, M., Ostrovsky, R.: Matching nuts and bolts. In: SODA, pp. 690\u2013696 (1994)"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B., Hell, P.: Sorting and graphs. In: Graphs and Order, Banff, Alta, 1984, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol.\u00a0147, pp. 169\u2013184. Reidel, Dordrecht (1985)","DOI":"10.1007\/978-94-009-5315-4_5"},{"issue":"1-3","key":"12_CR4","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0012-365X(98)00311-2","volume":"201","author":"G.R. Brightwell","year":"1999","unstructured":"Brightwell, G.R.: Balanced pairs in partial orders. Discrete Mathematics\u00a0201(1-3), 25\u201352 (1999)","journal-title":"Discrete Mathematics"},{"issue":"4","key":"12_CR5","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF01110378","volume":"2","author":"G.R. Brightwell","year":"1995","unstructured":"Brightwell, G.R., Felsner, S., Trotter, W.T.: Balancing pairs and the cross product conjecture. Order\u00a02(4), 327\u2013349 (1995)","journal-title":"Order"},{"issue":"3","key":"12_CR6","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF00383444","volume":"8","author":"G.R. Brightwell","year":"1991","unstructured":"Brightwell, G.R., Winkler, P.: Counting linear extensions. Order\u00a08(3), 225\u2013242 (1991)","journal-title":"Order"},{"issue":"7","key":"12_CR7","doi-asserted-by":"publisher","first-page":"2927","DOI":"10.1137\/090759860","volume":"39","author":"J. Cardinal","year":"2010","unstructured":"Cardinal, J., Fiorini, S., Joret, G., Jungers, R.M., Munro, J.I.: An efficient algorithm for partial order production. SIAM J. Comput.\u00a039(7), 2927\u20132940 (2010)","journal-title":"SIAM J. Comput."},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Cardinal, J., Fiorini, S., Joret, G., Jungers, R.M., Munro, J.I.: Sorting under partial information (without the ellipsoid algorithm). In: STOC, pp. 359\u2013368 (2010); To appear in Combinatorica","DOI":"10.1145\/1806689.1806740"},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/BF02122693","volume":"10","author":"I. Csisz\u00e1r","year":"1990","unstructured":"Csisz\u00e1r, I., K\u00f6rner, J., Lov\u00e1sz, L., Marton, K., Simonyi, G.: Entropy splitting for antiblocking corners and perfect graphs. Combinatorica\u00a010(1), 27\u201340 (1990)","journal-title":"Combinatorica"},{"issue":"3","key":"12_CR10","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1137\/070697720","volume":"40","author":"C. Daskalakis","year":"2011","unstructured":"Daskalakis, C., Karp, R.M., Mossel, E., Riesenfeld, S., Verbin, E.: Sorting and selection in posets. SIAM J. Comput.\u00a040(3), 597\u2013622 (2011)","journal-title":"SIAM J. Comput."},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/3-540-57529-4_75","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"D.P. Dubhashi","year":"1993","unstructured":"Dubhashi, D.P., Mehlhorn, K., Ranjan, D., Thiel, C.: Searching, sorting and randomised algorithms for central elements and ideal counting in posets. In: Shyamasundar, R.K. (ed.) FSTTCS 1993. LNCS, vol.\u00a0761, pp. 436\u2013443. Springer, Heidelberg (1993)"},{"issue":"4","key":"12_CR12","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1137\/0215077","volume":"15","author":"U. Faigle","year":"1986","unstructured":"Faigle, U., Lov\u00e1sz, L., Schrader, R., Tur\u00e1n, G.: Searching in trees, series-parallel and interval orders. SIAM J. Comput.\u00a015(4), 1075\u20131084 (1986)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"12_CR13","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1137\/0217007","volume":"17","author":"U. Faigle","year":"1988","unstructured":"Faigle, U., Tur\u00e1n, G.: Sorting and recognition problems for ordered sets. SIAM J. Comput.\u00a017(1), 100\u2013113 (1988)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"12_CR14","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1145\/321724.321729","volume":"19","author":"W.D. Frazer","year":"1972","unstructured":"Frazer, W.D., Bennett, B.T.: Bounds on optimal merge performance, and a strategy for optimality. J. ACM\u00a019(4), 641\u2013648 (1972)","journal-title":"J. ACM"},{"issue":"4","key":"12_CR15","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","volume":"1","author":"M.L. Fredman","year":"1976","unstructured":"Fredman, M.L.: How good is the information theory bound in sorting? Theor. Comput. Sci.\u00a01(4), 355\u2013361 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Huang, Z., Kannan, S., Khanna, S.: Algorithms for the generalized sorting problem. In: FOCS, pp. 738\u2013747 (2011)","DOI":"10.1109\/FOCS.2011.54"},{"issue":"3","key":"12_CR17","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1006\/jcss.1995.1077","volume":"51","author":"J. Kahn","year":"1995","unstructured":"Kahn, J., Kim, J.H.: Entropy and sorting. J. Comput. Syst. Sci.\u00a051(3), 390\u2013399 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/BF01275670","volume":"11","author":"J. Kahn","year":"1991","unstructured":"Kahn, J., Linial, N.: Balancing extensions via Brunn-Minkowski. Combinatorica\u00a011, 363\u2013368 (1991)","journal-title":"Combinatorica"},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/11523468_9","volume-title":"Automata, Languages and Programming","author":"K. Kaligosi","year":"2005","unstructured":"Kaligosi, K., Mehlhorn, K., Munro, J.I., Sanders, P.: Towards optimal multiple selection. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 103\u2013114. Springer, Heidelberg (2005)"},{"issue":"3","key":"12_CR20","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1137\/S0895480196304982","volume":"11","author":"J. Koml\u00f3s","year":"1998","unstructured":"Koml\u00f3s, J., Ma, Y., Szemer\u00e9di, E.: Matching nuts and bolts in o(n log n) time. SIAM J. Discrete Math.\u00a011(3), 347\u2013372 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"12_CR21","unstructured":"K\u00f6rner, J.: Coding of an information source having ambiguous alphabet and the entropy of graphs. In: Transactions of the 6th Prague Conference on Information Theory, pp. 411\u2013425 (1973)"},{"issue":"4","key":"12_CR22","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1137\/0213049","volume":"13","author":"N. Linial","year":"1984","unstructured":"Linial, N.: The information-theoretic bound is good for merging. SIAM J. Comput.\u00a013(4), 795\u2013801 (1984)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"12_CR23","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0097-3165(85)90087-1","volume":"40","author":"N. Linial","year":"1985","unstructured":"Linial, N., Saks, M.: Every poset has a central element. J. Comb. Theory, Ser. A\u00a040(2), 195\u2013210 (1985)","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"4","key":"12_CR24","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"J.S. Provan","year":"1983","unstructured":"Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput.\u00a012(4), 777\u2013788 (1983)","journal-title":"SIAM J. Comput."},{"key":"12_CR25","unstructured":"Rawlins, G.J.E.: Compared to what? - an introduction to the analysis of algorithms. Principles of computer science series. Computer Science Press (1992)"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Saks, M.E.: The information theoretic bound for problems on ordered sets and graphs. In: Graphs and order, Banff, Alta, 1984, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci, vol.\u00a0147, pp. 137\u2013168. Reidel, Dordrecht (1985)","DOI":"10.1007\/978-94-009-5315-4_4"},{"key":"12_CR27","unstructured":"Sch\u00f6nhage, A.: The production of partial orders. In: Journ\u00e9es Algorithmiques, \u00c9cole Norm. Sup., Paris, 1975, pp. 229\u2013246, Ast\u00e9risque, No. 38\u201339. Soc. Math., France (1976)"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Simonyi, G.: Graph entropy: a survey. In: Combinatorial Optimization (New Brunswick, NJ, 1992\u20131993. DIMACS Ser. Discrete Math. Theoret. Comput. Sci, vol.\u00a020, pp. 399\u2013441. Amer. Math. Soc., Providence (1995)","DOI":"10.1090\/dimacs\/020\/08"},{"issue":"1","key":"12_CR29","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0196-6774(87)90029-0","volume":"8","author":"G. Steiner","year":"1987","unstructured":"Steiner, G.: Searching in 2-dimensional partial orders. J. Algorithms\u00a08(1), 95\u2013105 (1987)","journal-title":"J. Algorithms"},{"issue":"4","key":"12_CR30","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1137\/0218047","volume":"18","author":"A.C. Yao","year":"1989","unstructured":"Yao, A.C.: On the complexity of partial order productions. SIAM J. Comput.\u00a018(4), 679\u2013689 (1989)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Space-Efficient Data Structures, Streams, and Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40273-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T10:44:04Z","timestamp":1558003444000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40273-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642402722","9783642402739"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40273-9_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}