{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T04:45:24Z","timestamp":1773809124274,"version":"3.50.1"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031231001","type":"print"},{"value":"9783031231018","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-23101-8_21","type":"book-chapter","created":{"date-parts":[[2022,12,19]],"date-time":"2022-12-19T20:18:53Z","timestamp":1671481133000},"page":"313-327","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Faster Algorithm for\u00a0Determining the\u00a0Linear Feasibility of\u00a0Systems of\u00a0BTVPI Constraints"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Wojciechowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Subramani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,1]]},"reference":[{"key":"21_CR1","volume-title":"Network Flows: Theory","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory. Prentice-Hall, Algorithms and Applications (1993)"},{"key":"21_CR2","doi-asserted-by":"publisher","unstructured":"\u00c0lvarez, C., Greenlaw, R.: A compendium of problems complete for symmetric logarithmic space. Electronic Colloquium on Computational Complexity (ECCC), vol. 3, no. 39 (1996). https:\/\/doi.org\/10.1007\/PL00001603","DOI":"10.1007\/PL00001603"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0024-3795(80)90162-7","volume":"34","author":"B Aspvall","year":"1980","unstructured":"Aspvall, B., Shiloach, Y.: A fast algorithm for solving systems of linear equations with two variables per equation. Linear Algebra Appl. 34, 117\u2013124 (1980)","journal-title":"Linear Algebra Appl."},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.disopt.2012.11.001","volume":"10","author":"R Chandrasekaran","year":"2013","unstructured":"Chandrasekaran, R., Subramani, K.: A combinatorial algorithm for Horn programs. Discret. Optim. 10, 85\u2013101 (2013)","journal-title":"Discret. Optim."},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Chandru, V., Hooker, J.N.: Optimization methods for logical inference. Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc. (1999)","DOI":"10.1002\/9781118033166"},{"issue":"6","key":"21_CR6","doi-asserted-by":"publisher","first-page":"1313","DOI":"10.1137\/S0097539791256325","volume":"23","author":"E Cohen","year":"1994","unstructured":"Cohen, E., Meggido, N.: Improved algorithms for linear inequalities with two variables per inequality. SIAM J. Comput. 23(6), 1313\u20131347 (1994)","journal-title":"SIAM J. Comput."},{"key":"21_CR7","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge, MA (2009)","edition":"3"},{"key":"21_CR8","unstructured":"CPLEX Manual. IBM ILOG CPLEX Optimization Studio V12.8.0 Documentation (2017)"},{"key":"21_CR9","doi-asserted-by":"publisher","DOI":"10.1515\/9781400884179","volume-title":"Linear Programming and Extensions","author":"GB Dantzig","year":"1963","unstructured":"Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton, NJ (1963)"},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/0097-3165(73)90004-6","volume":"14","author":"GB Dantzig","year":"1973","unstructured":"Dantzig, G.B., Eaves, B.C.: Fourier-motzkin elimination and its dual. J. Comb. Theor. (A) 14, 288\u2013297 (1973)","journal-title":"J. Comb. Theor. (A)"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Fiduccia, C.M., Mattheyses, R.M.: A linear time heuristics for improving network partitions. In: Proceedings of the 19th Design Automation Conference, pp. 175\u2013181 (1982)","DOI":"10.1109\/DAC.1982.1585498"},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02288320","volume":"13","author":"G Gallo","year":"1988","unstructured":"Gallo, G., Pallottino, S.: Shortest path algorithms. Ann. Oper. Res. 13, 1\u201379 (1988)","journal-title":"Ann. Oper. Res."},{"issue":"2","key":"21_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"Hochbaum, D.S., (Seffi) Naor, J.: Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput. 23(6), 1179\u20131192 (1994)","DOI":"10.1137\/S0097539793251876"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pp. 302\u2013311 (1984)","DOI":"10.1145\/800057.808695"},{"key":"21_CR16","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/11559306_9","volume-title":"Frontiers of Combining Systems","author":"SK Lahiri","year":"2005","unstructured":"Lahiri, S.K., Musuvathi, M.: An efficient decision procedure for UTVPI constraints. In: Gramlich, B. (ed.) FroCoS 2005. LNCS (LNAI), vol. 3717, pp. 168\u2013183. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11559306_9"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Luyo, L.E.F., Agra, A., Figueiredo, R., Anaya, E.O.: Mixed integer formulations for a routing problem with information collection in wireless networks. Eur. J. Oper. Res. 280(2), 621\u2013638 (2020)","DOI":"10.1016\/j.ejor.2019.06.054"},{"issue":"1","key":"21_CR18","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s10990-006-8609-1","volume":"19","author":"A Min\u00e9","year":"2006","unstructured":"Min\u00e9, A.: The octagon abstract domain. Higher-Order Symbolic Comput. 19(1), 31\u2013100 (2006)","journal-title":"Higher-Order Symbolic Comput."},{"key":"21_CR19","unstructured":"Nelson, C.G.: An $$n^o( \\log n)$$ algorithm for the two-variable-per-constraint linear program satisfiability problem. Technical Report Technical Note STA, Stanford University, Computer Science Department, pp. 78\u2013689 (1978)"},{"key":"21_CR20","unstructured":"Gurobi Optimization. Gurobi optimizer reference manual4. http:\/\/www.gurobi.com (2014)"},{"key":"21_CR21","unstructured":"Revesz, P.Z.: Tightened transitive closure of integer addition constraints. In: Symposium on Abstraction, Reformulation, and Approximation (SARA), pp. 136\u2013142 (2009)"},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"Singh, G., Gehr, T., P\u00fcschel, M., Vechev, M.T.: An abstract domain for certifying neural networks. PACMPL 3(POPL), 1\u201330 (2019)","DOI":"10.1145\/3290354"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Subramani, K., Wojciechowski, P.J.: A combinatorial certifying algorithm for linear feasibility in UTVPI constraints. Algorithmica 78(1), 166\u2013208 (2017)","DOI":"10.1007\/s00453-016-0131-1"},{"issue":"2","key":"21_CR24","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E Tardos","year":"1986","unstructured":"Tardos, E.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34(2), 250\u2013256 (1986)","journal-title":"Oper. Res."},{"key":"21_CR25","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1137\/1010063","volume":"10","author":"AF Veinott","year":"1968","unstructured":"Veinott, A.F., Dantzig, G.B.: Integral extreme points. SIAM Rev. 10, 371\u2013372 (1968)","journal-title":"SIAM Rev."},{"key":"21_CR26","doi-asserted-by":"crossref","unstructured":"Veinott, A.F., LiCalzi, M.: Subextremal functions and lattice programming, unpublished manuscript (1992)","DOI":"10.2139\/ssrn.877266"},{"key":"21_CR27","doi-asserted-by":"publisher","unstructured":"Vollmer, H.: Introduction to Circuit Complexity. Springer (1999). https:\/\/doi.org\/10.1007\/978-3-662-03927-4","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2023: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-23101-8_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T00:06:20Z","timestamp":1673049980000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-23101-8_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031231001","9783031231018"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-23101-8_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"1 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nov\u00fd Smokovec","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 January 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 January 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"48","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ics.science.upjs.sk\/sofsem2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"60% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3+","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6-7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}