{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:27:09Z","timestamp":1725488829924},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438656"},{"type":"electronic","value":"9783540454700"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45470-5_21","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T02:38:36Z","timestamp":1186886316000},"page":"217-230","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Identifying Simple and Quantified Lattice Points in the 2SAT Polytope"],"prefix":"10.1007","author":[{"given":"K.","family":"Subramani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,21]]},"reference":[{"unstructured":"Krzystof R. Apt and Ernst R. Olderog. Verification of Sequential and Concurrent Programs. Springer-Verlag, 1997.","key":"21_CR1"},{"doi-asserted-by":"crossref","unstructured":"Bengt Aspvall, Michael F. Plass, and Robert Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, (3), 1979.","key":"21_CR2","DOI":"10.1016\/0020-0190(79)90002-4"},{"doi-asserted-by":"crossref","unstructured":"Bengt Aspvall and Yossi Shiloach. A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality. In 20th Annual Symposium on Foundations of Computer Science, pages 205\u2013217, San Juan, Puerto Rico, 29\u201331 October 1979. IEEE.","key":"21_CR3","DOI":"10.1109\/SFCS.1979.1"},{"doi-asserted-by":"crossref","unstructured":"V. Chandru and J. N. Hooker. Optimization Methods for Logical Inference. Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., 1999.","key":"21_CR4","DOI":"10.1002\/9781118033166"},{"doi-asserted-by":"crossref","unstructured":"Z. Chen. A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-cnf formula. Information Processing Letters, pages 191\u2013193, 1992.","key":"21_CR5","DOI":"10.1016\/0020-0190(92)90199-6"},{"unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press and McGraw-Hill Book Company, 6th edition, 1992.","key":"21_CR6"},{"doi-asserted-by":"crossref","unstructured":"S.A. Cook and M. Luby. A simple parallel algorithm for finding a satisfying truth assignment to a 2-cnf formula. Information Processing Letters, pages 141\u2013145, 1988.","key":"21_CR7","DOI":"10.1016\/0020-0190(88)90069-5"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/0097-3165(73)90004-6","volume":"14","author":"G. B. Dantzig","year":"1973","unstructured":"G. B. Dantzig and B. C. Eaves. Fourier-Motzkin Elimination and its Dual. Journal of Combinatorial Theory (A), 14:288\u2013297, 1973.","journal-title":"Journal of Combinatorial Theory (A)"},{"unstructured":"J. B. J. Fourier. Reported in: Analyse de travaux de l\u2019Academie Royale des Sciences, pendant l\u2019annee 1824, Partie Mathematique, Historyde l\u2019Academie Royale de Sciences de l\u2019Institue de France 7 (1827) xlvii-lv. (Partial English translation in: D.A. Kohler, Translation of a Report by Fourier on his work on Linear Inequalities. Opsearch 10 (1973) 38\u201342.). Academic Press, 1824.","key":"21_CR9"},{"doi-asserted-by":"crossref","unstructured":"F. Gavril. An efficiently solvable graph partition, problem to which many problems are reducible. Information Processing Letters, pages 285\u2013290, 1993.","key":"21_CR10","DOI":"10.1016\/0020-0190(93)90038-B"},{"unstructured":"Michael Genesereth. Logical Foundations of Artificial Intelligence. Morgan Kaufmann, 1990.","key":"21_CR11"},{"key":"21_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman Company, San Francisco, 1979."},{"key":"21_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/3-540-53162-9_34","volume-title":"Proceedings Second International Conference on Algebraic and Logic Programming","author":"T. Huynh","year":"1990","unstructured":"Tien Huynh, Catherine Lassez, and Jean-Louis Lassez. Fourier Algorithm Revisited. In H\u00e9l\u00e8ne Kirchner and W. Wechler, editors, Proceedings Second International Conference on Algebraic and Logic Programming, volume 463 of Lecture Notes in Computer Science, pages 117\u2013131, Nancy, France, October 1990. Springer-Verlag."},{"issue":"6","key":"21_CR14","doi-asserted-by":"crossref","first-page":"1179","DOI":"10.1137\/S0097539793251876","volume":"23","author":"S. Dorit","year":"1994","unstructured":"Dorit S. Hochbaum and Joseph (Seffi) Naor. Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM Journal on Computing, 23(6):1179\u20131192, December 1994.","journal-title":"SIAM Journal on Computing"},{"unstructured":"Hochbaum, editor. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1996.","key":"21_CR15"},{"key":"21_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-21708-5","volume-title":"Combinatorial Optimization","author":"B. Korte","year":"2000","unstructured":"B. Korte and J. Vygen. Combinatorial Optimization. Number 21. Springer-Verlag, New York, 2000."},{"unstructured":"Jean-Louis Lassez and Michael Maher. On fourier\u2019s algorithm for linear constraints. Journal of Automated Reasoning, to appear, 1991.","key":"21_CR17"},{"unstructured":"Jacques Loeckx and Kurt Sieber. The Foundations of Program Verification. John Wiley and Sons, 1985.","key":"21_CR18"},{"unstructured":"Nils J. Nilsson. Artificial Intelligence: A New Synthesis. Morgan Kaufmann, 1998.","key":"21_CR19"},{"key":"21_CR20","first-page":"48","volume":"6","author":"G. L. Nemhauser","year":"1974","unstructured":"G. L. Nemhauser and L. E. Trotter Jr. Properties of vertex packing and independence system polyhedra. mathprog, 6:48\u201361, 1974.","journal-title":"mathprog"},{"key":"21_CR21","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G. L. Nemhauser","year":"1975","unstructured":"G. L. Nemhauser and J. L. E. Trotter. Vertex packing: structural properties and algorithms. Mathematical Programming, 8:232\u2013248, 1975.","journal-title":"Mathematical Programming"},{"key":"21_CR22","volume-title":"Integer and Combinatorial Optimization","author":"G. L. Nemhauser","year":"1999","unstructured":"G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. John Wiley & Sons, New York, 1999."},{"key":"21_CR23","volume-title":"Computational Complexity","author":"C. H. Papadimitriou","year":"1994","unstructured":"Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, New York, 1994."},{"doi-asserted-by":"crossref","unstructured":"T.J. Schaefer. The complexity of satisfiability problems. In Alfred Aho, editor, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pages 216\u2013226, New York City, NY, 1978. ACM Press.","key":"21_CR24","DOI":"10.1145\/800133.804350"},{"key":"21_CR25","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1987","unstructured":"Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, New York, 1987."},{"issue":"4","key":"21_CR26","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1145\/322276.322288","volume":"28","author":"Robert Shostak","year":"1981","unstructured":"Robert Shostak. Deciding linear inequalities by computing loop residues. Journal of the ACM, 28(4):769\u2013779, October 1981.","journal-title":"Journal of the ACM"},{"unstructured":"K. Subramani. An analysis os selected qips, 2002. Submitted to Journal of Logic and Computation.","key":"21_CR27"},{"unstructured":"K. Subramani. A polynomial time algorithm for a class of quantified linear programs, 2002. Submitted to Mathematical Programming.","key":"21_CR28"},{"key":"21_CR29","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1137\/1010063","volume":"10","author":"A.F. Veinott","year":"1968","unstructured":"A.F. Veinott and G.B. Dantzig. Integral extreme points. SIAM Review, 10:371\u2013372, 1968.","journal-title":"SIAM Review"},{"doi-asserted-by":"crossref","unstructured":"V. Chandru and M.R. Rao. Linear programming. In Algorithms and Theory of Computation Handbook, CRC Press, 1999. CRC Press, 1999.","key":"21_CR30","DOI":"10.1201\/9781420049503-c32"},{"doi-asserted-by":"crossref","unstructured":"H.P. Williams. Fourier-motzkin elimination extension to integer programming. J. Combinatorial Theory, (21):118\u2013123, 1976.","key":"21_CR31","DOI":"10.1016\/0097-3165(76)90055-8"},{"doi-asserted-by":"crossref","unstructured":"H.P. Williams. A characterisation of all feasible solutions to an integer program. Discrete Appl. Math., (5):147\u2013155, 1983.","key":"21_CR32","DOI":"10.1016\/0166-218X(83)90024-0"}],"container-title":["Lecture Notes in Computer Science","Artificial Intelligence, Automated Reasoning, and Symbolic Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45470-5_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T10:23:47Z","timestamp":1558261427000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45470-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438656","9783540454700"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-45470-5_21","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"21 June 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}