{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T11:56:21Z","timestamp":1772366181927,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T00:00:00Z","timestamp":1192752000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,6]]},"DOI":"10.1007\/s00453-007-9090-x","type":"journal-article","created":{"date-parts":[[2007,10,18]],"date-time":"2007-10-18T13:49:58Z","timestamp":1192715398000},"page":"200-235","source":"Crossref","is-referenced-by-count":13,"title":["Unique Sink Orientations of Grids"],"prefix":"10.1007","volume":"51","author":[{"given":"Bernd","family":"G\u00e4rtner","sequence":"first","affiliation":[]},{"given":"Walter D.","family":"Jr. Morris","sequence":"additional","affiliation":[]},{"given":"Leo","family":"R\u00fcst","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,19]]},"reference":[{"issue":"1","key":"9090_CR1","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1287\/moor.1.1.89","volume":"1","author":"I. Adler","year":"1976","unstructured":"Adler, I., Saigal, R.: Long monotone paths in abstract polytopes. Math. Oper. Res. 1(1), 89\u201395 (1976)","journal-title":"Math. Oper. Res."},{"key":"9090_CR2","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, H., Sandberg, S., Vorobyov, S.: Randomized subexponential algorithms for parity games. Technical Report TR-2003-019, Department of Information Technology, Uppsala University (2003)","DOI":"10.1007\/3-540-36494-3_58"},{"key":"9090_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1007\/978-3-540-28629-5_52","volume-title":"Proc. 29th International Symposium on Mathematical Foundations of Computer Science (MFCS)","author":"H. Bj\u00f6rklund","year":"2004","unstructured":"Bj\u00f6rklund, H., Sandberg, S., Vorobyov, S.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. In: Proc. 29th International Symposium on Mathematical Foundations of Computer Science (MFCS). Lecture Notes in Computer Science, vol. 3153, pp. 673\u2013685. Springer, Berlin (2004)"},{"key":"9090_CR4","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/BF01830678","volume":"34","author":"R. Blind","year":"1987","unstructured":"Blind, R., Mani-Levitska, P.: On puzzles and polytope isomorphisms. Aequ. Math. 34, 287\u2013297 (1987)","journal-title":"Aequ. Math."},{"key":"9090_CR5","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1006\/jagm.1996.0060","volume":"21","author":"B. Chazelle","year":"1996","unstructured":"Chazelle, B., Matou\u0161ek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms 21, 579\u2013597 (1996)","journal-title":"J. Algorithms"},{"key":"9090_CR6","volume-title":"Linear Programming","author":"V. Chv\u00e1tal","year":"1983","unstructured":"Chv\u00e1tal, V.: Linear Programming. Freeman, New York (1983)"},{"key":"9090_CR7","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"K.L. Clarkson","year":"1995","unstructured":"Clarkson, K.L.: Las Vegas algorithms for linear and integer programming. J. ACM 42, 488\u2013499 (1995)","journal-title":"J. ACM"},{"key":"9090_CR8","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1090\/dimacs\/013\/04","volume-title":"Advances in Computational Complexity Theory","author":"A. Condon","year":"1993","unstructured":"Condon, A.: On algorithms for simple stochastic games. In: Cai, J.-Y. (ed.) Advances in Computational Complexity Theory. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 51\u201373. American Mathematical Society, Providence (1993)"},{"key":"9090_CR9","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0021-9800(70)80010-2","volume":"8","author":"R.W. Cottle","year":"1970","unstructured":"Cottle, R.W., Dantzig, G.B.: A generalization of the linear complementarity problem. J. Comb. Theory 8, 79\u201390 (1970)","journal-title":"J. Comb. Theory"},{"key":"9090_CR10","volume-title":"The Linear Complementarity Problem","author":"R.W. Cottle","year":"1992","unstructured":"Cottle, R.W., Pang, J., Stone, R.E.: The Linear Complementarity Problem. Academic, San Diego (1992)"},{"key":"9090_CR11","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1515\/advg.2004.4.4.459","volume":"4","author":"M. Develin","year":"2004","unstructured":"Develin, M.: LP-orientations of cubes and crosspolytopes. Adv. Geom. 4, 459\u2013468 (2004)","journal-title":"Adv. Geom."},{"key":"9090_CR12","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0024-3795(95)00091-5","volume":"223\/224","author":"A.A. Ebiefung","year":"1995","unstructured":"Ebiefung, A.A.: Existence theory and Q-matrix characterization for the generalized linear complementarity problem. Linear Algebra Appl. 223\/224, 155\u2013169 (1995)","journal-title":"Linear Algebra Appl."},{"key":"9090_CR13","unstructured":"Ebiefung, A.A.: Existence theory and Q-matrix characterization for the generalized linear complementarity problem: Revisited. Manuscript (2005)"},{"key":"9090_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4044-0","volume-title":"Combinatorial Convexity and Algebraic Geometry","author":"G. Ewald","year":"1996","unstructured":"Ewald, G.: Combinatorial Convexity and Algebraic Geometry. Springer, Berlin (1996)"},{"issue":"3","key":"9090_CR15","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s00454-005-1187-x","volume":"34","author":"S. Felsner","year":"2005","unstructured":"Felsner, S., G\u00e4rtner, B., Tschirschnitz, F.: Grid orientations, (d,d+2)-polytopes, and arrangements of pseudolines. Discrete Comput. Geom. 34(3), 411\u2013437 (2005)","journal-title":"Discrete Comput. Geom."},{"issue":"4&5","key":"9090_CR16","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1142\/S0218195904001500","volume":"14","author":"K. Fischer","year":"2004","unstructured":"Fischer, K., G\u00e4rtner, B.: The smallest enclosing ball of balls: combinatorial structure and algorithms. Int. J. Comput. Geom. Appl. 14(4&5), 341\u2013378 (2004)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9090_CR17","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner, B.: The Random-Facet simplex algorithm on combinatorial cubes. Random Struct. Algorithms 20(3), (2002)","DOI":"10.1002\/rsa.10034"},{"key":"9090_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/11537311_19","volume-title":"Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT)","author":"B. G\u00e4rtner","year":"2005","unstructured":"G\u00e4rtner, B., R\u00fcst, L.: Simple stochastic games and P-matrix generalized linear complementarity problems. In: Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT). Lecture Notes in Computer Science, vol. 3623, pp. 209\u2013220. Springer, Berlin (2005)"},{"key":"9090_CR19","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner, B., Schurr, I.: Linear programming and unique sink orientations. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 749\u2013757, 2006","DOI":"10.1145\/1109557.1109639"},{"key":"9090_CR20","series-title":"Lecture Notes in Computer Science","first-page":"669","volume-title":"Proc. 13th Ann. ACM Symp. Theoretical Aspects of Computer Science","author":"B. G\u00e4rtner","year":"1996","unstructured":"G\u00e4rtner, B., Welzl, E.: Linear programming\u2014randomization and abstract frameworks. In: Proc. 13th Ann. ACM Symp. Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 1046, pp. 669\u2013687. Springer, Berlin (1996)"},{"key":"9090_CR21","series-title":"Lecture Notes in Computer Science","first-page":"26","volume-title":"Lecture Notes of the Graduate Program Computational Discrete Mathematics","author":"B. G\u00e4rtner","year":"2001","unstructured":"G\u00e4rtner, B., Welzl, E.: Explicit and implicit enforcing\u2014randomized optimization. In: Lecture Notes of the Graduate Program Computational Discrete Mathematics. Lecture Notes in Computer Science, vol. 2122, pp. 26\u201349. Springer, Berlin (2001)"},{"issue":"4","key":"9090_CR22","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1002\/rsa.10099","volume":"23","author":"B. G\u00e4rtner","year":"2003","unstructured":"G\u00e4rtner, B., Solymosi, J., Tschirschnitz, F., Valtr, P., Welzl, E.: One line and n points. Random Struct. Algorithms 23(4), 453\u2013471 (2003) (preliminary version at STOC 2001)","journal-title":"Random Struct. Algorithms"},{"key":"9090_CR23","series-title":"Lecture Notes in Computer Science","volume-title":"Proc. 14th Annual European Symposium on Algorithms (ESA)","author":"B. G\u00e4rtner","year":"2006","unstructured":"G\u00e4rtner, B., Matou\u0161ek, J., R\u00fcst, L., \u0160kovro\u0148, P.: Violator spaces: structure and algorithms. In: Proc. 14th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science. Springer, Berlin (2006)"},{"key":"9090_CR24","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF01442864","volume":"6","author":"P. Gordan","year":"1873","unstructured":"Gordan, P.: \u00dcber die Aufl\u00f6sung linearer Gleichungen mit reellen Coefficienten. Math. Ann. 6, 23\u201328 (1873)","journal-title":"Math. Ann."},{"key":"9090_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-36387-4","volume-title":"Automata, Logics, and Infinite Games","author":"E. Gr\u00e4del","year":"2002","unstructured":"Gr\u00e4del, E., Thomas, W., Wilke, T.: Automata, Logics, and Infinite Games. Lecture Notes in Computer Science, vol.\u00a02500. Springer, Berlin (2002)"},{"key":"9090_CR26","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0166-218X(88)90042-X","volume":"20","author":"K.W. Hoke","year":"1988","unstructured":"Hoke, K.W.: Completely unimodal numberings of a simple polytope. Discrete Appl. Math. 20, 69\u201381 (1988)","journal-title":"Discrete Appl. Math."},{"key":"9090_CR27","series-title":"Contemporary Mathematics","volume-title":"Advances in Discrete and Computational Geometry","author":"F. Holt","year":"1998","unstructured":"Holt, F., Klee, V.: A proof of the strict monotone 4-step conjecture. In: Chazelle, J., Goodman, J.B., Pollack, R. (eds.) Advances in Discrete and Computational Geometry. Contemporary Mathematics. Am. Math. Soc., Providence (1998)"},{"key":"9090_CR28","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/0097-3165(88)90064-7","volume":"49","author":"G. Kalai","year":"1988","unstructured":"Kalai, G.: A simple way to tell a simple polytope from its graph. J. Comb. Theory 49, 381\u2013383 (1988)","journal-title":"J. Comb. Theory"},{"key":"9090_CR29","first-page":"217","volume":"79","author":"G. Kalai","year":"1997","unstructured":"Kalai, G.: Linear programming, the simplex algorithm and simple polytopes. Math. Program. 79, 217\u2013233 (1997)","journal-title":"Math. Program."},{"key":"9090_CR30","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1090\/S0273-0979-1992-00285-9","volume":"26","author":"G. Kalai","year":"1992","unstructured":"Kalai, G., Kleitman, D.J.: A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull. Am. Math. Soc. 26, 315\u2013316 (1992)","journal-title":"Bull. Am. Math. Soc."},{"key":"9090_CR31","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"L.G. Khachiyan","year":"1980","unstructured":"Khachiyan, L.G.: Polynomial algorithms in linear programming. USSR Comput. Math. Math. Phys. 20, 53\u201372 (1980)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"9090_CR32","first-page":"159","volume-title":"Inequalities III","author":"V. Klee","year":"1972","unstructured":"Klee, V., Minty, G.J.: How good is the simplex algorithm? In: Shisha, O. (ed.) Inequalities III, pp. 159\u2013175. Academic, San Diego (1972)"},{"key":"9090_CR33","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/BF02711519","volume":"15","author":"P. Kleinschmidt","year":"1996","unstructured":"Kleinschmidt, P., Onn, S.: Signable posets and partitionable simplicial complexes. Discrete Comput. Geom. 15, 443\u2013466 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"9090_CR34","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1006\/inco.1995.1035","volume":"117","author":"W. Ludwig","year":"1995","unstructured":"Ludwig, W.: A subexponential randomized algorithm for the simple stochastic game problem. Inform. Comput. 117, 151\u2013155 (1995)","journal-title":"Inform. Comput."},{"issue":"4","key":"9090_CR35","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1002\/rsa.3240050408","volume":"5","author":"J. Matou\u0161ek","year":"1994","unstructured":"Matou\u0161ek, J.: Lower bounds for a subexponential optimization algorithm. Random Struct. Algorithms 5(4), 591\u2013607 (1994)","journal-title":"Random Struct. Algorithms"},{"key":"9090_CR36","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1007\/BF01940877","volume":"16","author":"J. Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J., Sharir, M., Welzl, E.: A subexponential bound for linear programming. Algorithmica 16, 498\u2013516 (1996)","journal-title":"Algorithmica"},{"key":"9090_CR37","unstructured":"Megiddo, N.: A note on the complexity of P-matrix LCP and computing an equilibrium. Technical Report, IBM Almaden Research Center, San Jose (1988)"},{"key":"9090_CR38","unstructured":"Morris, W.D. Jr.: Distinguishing cube orientations arising from linear programs. Manuscript (2002)"},{"issue":"2","key":"9090_CR39","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1137\/S0036144502420083","volume":"46","author":"U. Sch\u00e4fer","year":"2004","unstructured":"Sch\u00e4fer, U.: A linear complementarity problem with a P-matrix. SIAM Rev. 46(2), 189\u2013201 (2004)","journal-title":"SIAM Rev."},{"key":"9090_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/11496915_17","volume-title":"Proc. 11th Conference on Integer Programming and Combinatorial Optimization (IPCO)","author":"I. Schurr","year":"2005","unstructured":"Schurr, I., Szab\u00f3, T.: Jumping doesn\u2019t help in abstract cubes. In: Proc. 11th Conference on Integer Programming and Combinatorial Optimization (IPCO). Lecture Notes in Computer Science, vol. 3509, pp. 225\u2013235. Springer, Berlin (2005)"},{"key":"9090_CR41","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BF02574699","volume":"6","author":"R. Seidel","year":"1991","unstructured":"Seidel, R.: Small-dimensional linear programming and convex hulls made easy. Discrete Comput. Geom. 6, 423\u2013434 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"9090_CR42","unstructured":"Sloane, N.J.A.: Sequence A000522. The On-Line Encyclopedia of Integer Sequences, http:\/\/www.research.att.com\/~njas\/sequences\/ (2004)"},{"key":"9090_CR43","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1287\/moor.3.4.322","volume":"3","author":"A. Stickney","year":"1978","unstructured":"Stickney, A., Watson, L.: Digraph models of Bard-type algorithms for the linear complementarity problem. Math. Oper. Res. 3, 322\u2013333 (1978)","journal-title":"Math. Oper. Res."},{"key":"9090_CR44","first-page":"340","volume":"76","author":"E. Stiemke","year":"1915","unstructured":"Stiemke, E.: \u00dcber positive L\u00f6sungen homogener linearer Gleichungen. J. Reine Angew. Math. 76, 340\u2013342 (1915)","journal-title":"J. Reine Angew. Math."},{"key":"9090_CR45","unstructured":"Szab\u00f3, T., Welzl, E.: Unique sink orientations of cubes. In: Proc. 42nd IEEE Symp. on Foundations of Comput. Sci., pp. 547\u2013555, 2000"},{"key":"9090_CR46","unstructured":"Tschirschnitz, F.: LP-related properties of polytopes with few facets. PhD Thesis, ETH Z\u00fcrich (2003)"},{"key":"9090_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BFb0038202","volume-title":"New Results and New Trends in Computer Science","author":"E. Welzl","year":"1991","unstructured":"Welzl, E.: Smallest enclosing disks (balls and ellipsoids). In: Maurer, H. (ed.) New Results and New Trends in Computer Science. Lecture Notes in Computer Science, vol. 555, pp. 359\u2013370. Springer, Berlin (1991)"},{"key":"9090_CR48","first-page":"165","volume":"50","author":"D. Wiedemann","year":"1985","unstructured":"Wiedemann, D.: Unimodal set-functions. Congr. Numer. 50, 165\u2013169 (1985)","journal-title":"Congr. Numer."},{"key":"9090_CR49","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-8431-1","volume-title":"Lectures on Polytopes","author":"G.M. Ziegler","year":"1995","unstructured":"Ziegler, G.M.: Lectures on Polytopes. Springer, Berlin (1995)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9090-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9090-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9090-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:00Z","timestamp":1559123100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9090-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,19]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["9090"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9090-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,19]]}}}