{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:47Z","timestamp":1787337467165,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"It is not known if planar integer linear programming is P-complete or if it is in NC, and the same can be said about the computation of the remainder sequence of the Euclidean algorithm applied to two integers. However, both computations are NC equivalent. The latter computational problem was reduced in NC to the former one by Deng [Mathematical Programming: Complexity and Application, Ph.D. dissertation, Stanford University, Stanford, CA, 1989; Proc. ACM Symp. on Parallel Algorithms and Architectures, 1989,pp. 110--116]. We now prove the converse NC-reduction.<\/jats:p>","DOI":"10.1137\/s0097539794276841","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"960-971","source":"Crossref","is-referenced-by-count":1,"title":["Planar Integer Linear Programming is NC Equivalent to Euclidean GCD"],"prefix":"10.1137","volume":"27","author":[{"given":"D. F.","family":"Shallcross","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"V. Y.","family":"Pan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Y.","family":"Lin-Kriz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"A. Aho, D\u017e. Hopkroft, D\u017e. Ulp\u00b8man, Postroenie i analiz vychislitelnykh algoritmov, \u201cMir\u201d, 1979, 536\u20130, Translated by A. O. Slisenko; Edited by Ju. V. Matijasevi\u010d80g:68036"},{"key":"R2","unstructured":"X. Deng,\n Mathematical Programming: Complexity and Application\n , Ph.D. dissertation, Stanford University, Stanford, CA, 1989."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"X. Deng,\n On parallel complexity of integer linear programming\n , in Proc. ACM Symp. on Parallel Algorithms and Architectures, Association for Computing Machinery, New York, 1989, pp. 110\u2013116.","DOI":"10.1145\/72935.72948"},{"key":"R4","unstructured":"A. Gibbons, W. Rytter,\n Efficient Parallel Algorithms\n , Cambridge University Press, London, 1988."},{"key":"R5","unstructured":"R. Greenlaw, H. J. Hoover, and W. L. Ruzzo,\n A compendium of problems complete for P\n , Tech. report TR 91\u201011, Dept. of Computer Science, University of Alberta, Edmonton; Tech. report TR 99\u201005\u201001, CS and Engineering Dept., University of Washington, Seattle, 1991."},{"key":"R6","unstructured":"R. Greenlaw,\n Polynomial completeness and parallel computation\n , in Synthesis of Parallel Algorithms J. H. Reif, Ed., Morgan\u2010Kaufman Publishers, San Mateo, CA, 1993, pp. 901\u2013954."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/322169.322179"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"R. Kannan,\n Improved algorithms for integer linear programming and related lattice problems\n , in Proc. 15th Annual ACM Symp. on Theory of Computing, Association for Computing Machinery, New York, 1983, pp. 193\u2013206.","DOI":"10.1145\/800061.808749"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90008-4"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"R. M. Karp and V. Ramachandran,\n A survey of parallel algorithms for shared\u2010memory machines\n , in Handbook of Theoretical Computer Science, North\u2013Holland, Amsterdam, 1990, pp. 869\u2013941.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"R11","volume-title":"The art of computer programming. Vol. 2","author":"Knuth Donald","year":"1981"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"R13","unstructured":"Yu Lin\u2010Kriz, Victor Pan, On parallel complexity of integer linear programming, GCD and the iterated mod function, ACM, New York, 1992, 124\u201313793f:90119"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"David Shallcross, Victor Pan, Yu Lin\u2010Kriz, The NC equivalence of planar integer linear programming and Euclidean GCD, IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, 557\u20135641328450","DOI":"10.1109\/SFCS.1993.366831"},{"key":"R15","unstructured":"A. Skhrei\u02d8ver, Teoriya lineinogo i tselochislennogo programmirovaniya. 2, \u201cMir\u201d, 1991, 361\u2013704, Translated from the English by S. A. Tarasov, M. A. Frumkin and V. I. Shlyk; Translation edited by L. G. Khachiyan94g:90005"},{"key":"R16","first-page":"1132","volume":"20","author":"Zamanski L.","year":"1984","journal-title":"\u00c8konom. i Mat. Metody"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794276841","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:11:59Z","timestamp":1787335919000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794276841"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794276841"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794276841","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}