{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T18:02:49Z","timestamp":1742925769253,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031682780"},{"type":"electronic","value":"9783031682797"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-68279-7_12","type":"book-chapter","created":{"date-parts":[[2024,8,11]],"date-time":"2024-08-11T23:03:07Z","timestamp":1723417387000},"page":"193-206","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Using Matrix Sparsification to\u00a0Solve Tropical Linear Vector Equations"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3070-9355","authenticated-orcid":false,"given":"Nikolai","family":"Krivulin","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,12]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","unstructured":"Akian, M., Gaubert, S., Guterman, A.: Tropical polyhedra are equivalent to mean payoff games. Int. J. Algebra Comput. 22(1), 1250001\u20131\u20131250001\u201343 (2012). https:\/\/doi.org\/10.1142\/S0218196711006674","DOI":"10.1142\/S0218196711006674"},{"issue":"2","key":"12_CR2","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/s00454-012-9469-6","volume":"49","author":"X Allamigeon","year":"2013","unstructured":"Allamigeon, X., Gaubert, S., Goubault, E.: Computing the vertices of tropical polyhedra using directed hypergraphs. Discrete Comput. Geom. 49(2), 247\u2013279 (2013). https:\/\/doi.org\/10.1007\/s00454-012-9469-6","journal-title":"Discrete Comput. Geom."},{"key":"12_CR3","doi-asserted-by":"publisher","unstructured":"Butkovi\u010d, P.: On properties of solution sets of extremal linear programs. In: Burkard, R.E., Cuninghame-Green, R.A., Zimmermann, U. (eds.) Algebraic and Combinatorial Methods in Operations Research, North-Holland Mathematics Studies, vol.\u00a095, pp. 41\u201354. North-Holland (1984). https:\/\/doi.org\/10.1016\/S0304-0208(08)72952-9","DOI":"10.1016\/S0304-0208(08)72952-9"},{"key":"12_CR4","unstructured":"Butkovi\u010d, P.: On certain properties of the systems of linear extremal equations. Ekonom.-Mat. Obzor 14(1), 72\u201378 (1978)"},{"key":"12_CR5","unstructured":"Butkovi\u010d, P.: Solution of systems of linear extremal equations. Ekonom.-Mat. Obzor 17(4), 402\u2013416 (1981)"},{"key":"12_CR6","doi-asserted-by":"publisher","unstructured":"Butkovi\u010d, P.: Max-linear Systems. Springer Monographs in Mathematics, Springer, London (2010). https:\/\/doi.org\/10.1007\/978-1-84996-299-5","DOI":"10.1007\/978-1-84996-299-5"},{"key":"12_CR7","unstructured":"Butkovi\u010d, P., Heged\u00fcs, G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonom.-Mat. Obzor 20(2), 203\u2013215 (1984)"},{"issue":"3","key":"12_CR8","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/j.dam.2005.09.008","volume":"154","author":"P Butkovi\u010d","year":"2006","unstructured":"Butkovi\u010d, P., Zimmermann, K.: A strongly polynomial algorithm for solving two-sided linear systems in max-algebra. Discrete Appl. Math. 154(3), 437\u2013446 (2006). https:\/\/doi.org\/10.1016\/j.dam.2005.09.008","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(02)00228-1","volume":"293","author":"RA Cuninghame-Green","year":"2003","unstructured":"Cuninghame-Green, R.A., Butkovic, P.: The equation $${A}\\otimes x={B}\\otimes y$$ over (max,+). Theoret. Comput. Sci. 293(1), 3\u201312 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(02)00228-1","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"12_CR10","first-page":"729","volume":"42","author":"RA Cuninghame-Green","year":"2001","unstructured":"Cuninghame-Green, R.A., Zimmermann, K.: Equation with residuated functions. Comment. Math. Univ. Carolin. 42(4), 729\u2013740 (2001)","journal-title":"Comment. Math. Univ. Carolin."},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4171\/dm\/154","volume":"9","author":"M Develin","year":"2004","unstructured":"Develin, M., Sturmfels, B.: Tropical convexity. Doc. Math. 9, 1\u201327 (2004)","journal-title":"Doc. Math."},{"issue":"5","key":"12_CR12","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1016\/j.laa.2009.03.012","volume":"431","author":"S Gaubert","year":"2009","unstructured":"Gaubert, S., Katz, R.D.: The tropical analogue of polar cones. Linear Algebra Appl. 431(5), 608\u2013625 (2009). https:\/\/doi.org\/10.1016\/j.laa.2009.03.012","journal-title":"Linear Algebra Appl."},{"issue":"12","key":"12_CR13","doi-asserted-by":"publisher","first-page":"1447","DOI":"10.1016\/j.jsc.2011.12.049","volume":"47","author":"S Gaubert","year":"2012","unstructured":"Gaubert, S., Katz, R.D., Sergeev, S.: Tropical linear-fractional programming and parametric mean payoff games. J. Symbolic Comput. 47(12), 1447\u20131478 (2012). https:\/\/doi.org\/10.1016\/j.jsc.2011.12.049","journal-title":"J. Symbolic Comput."},{"key":"12_CR14","doi-asserted-by":"publisher","unstructured":"Golan, J.S.: Semirings and Affine Equations Over Them, Mathematics and Its Applications, vol.\u00a0556. Kluwer Acad. Publ., Dordrecht (2003). https:\/\/doi.org\/10.1007\/978-94-017-0383-3","DOI":"10.1007\/978-94-017-0383-3"},{"key":"12_CR15","doi-asserted-by":"publisher","unstructured":"Gondran, M., Minoux, M.: Graphs, Dioids and Semirings, Operations Research\/ Computer Science Interfaces, vol.\u00a041. Springer, New York (2008). https:\/\/doi.org\/10.1007\/978-0-387-75450-5","DOI":"10.1007\/978-0-387-75450-5"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Heidergott, B., Olsder, G.J., van der Woude, J.: Max Plus at Work. Princeton series in applied mathematics. Princeton Univ. Press, Princeton (2006)","DOI":"10.1515\/9781400865239"},{"issue":"3","key":"12_CR17","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/j.dam.2018.06.011","volume":"254","author":"D Jones","year":"2019","unstructured":"Jones, D.: On two-sided max-linear equations. Discrete Appl. Math. 254(3), 146\u2013160 (2019). https:\/\/doi.org\/10.1016\/j.dam.2018.06.011","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"12_CR18","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1134\/S1063454123020103","volume":"56","author":"NK Krivulin","year":"2023","unstructured":"Krivulin, N.K.: On the solution of a two-sided vector equation in tropical algebra. Vestnik St. Petersburg Univ. Math. 56(2), 172\u2013181 (2023). https:\/\/doi.org\/10.1134\/S1063454123020103","journal-title":"Vestnik St. Petersburg Univ. Math."},{"issue":"1","key":"12_CR19","doi-asserted-by":"publisher","first-page":"66","DOI":"10.3103\/S1063454118010065","volume":"51","author":"NK Krivulin","year":"2018","unstructured":"Krivulin, N.K., Sorokin, V.N.: Solution of a multidimensional tropical optimization problem using matrix sparsification. Vestnik St. Petersburg Univ. Math. 51(1), 66\u201376 (2018). https:\/\/doi.org\/10.3103\/S1063454118010065","journal-title":"Vestnik St. Petersburg Univ. Math."},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.laa.2014.06.044","volume":"468","author":"N Krivulin","year":"2015","unstructured":"Krivulin, N.: Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468, 211\u2013232 (2015). https:\/\/doi.org\/10.1016\/j.laa.2014.06.044","journal-title":"Linear Algebra Appl."},{"issue":"5","key":"12_CR21","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1080\/02331934.2013.840624","volume":"64","author":"N Krivulin","year":"2015","unstructured":"Krivulin, N.: A multidimensional tropical optimization problem with a non-linear objective function and linear constraints. Optimization 64(5), 1107\u20131129 (2015). https:\/\/doi.org\/10.1080\/02331934.2013.840624","journal-title":"Optimization"},{"key":"12_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-319-24704-5_20","volume-title":"Relational and Algebraic Methods in Computer Science","author":"N Krivulin","year":"2015","unstructured":"Krivulin, N.: Solving a tropical optimization problem via matrix sparsification. In: Kahl, W., Winter, M., Oliveira, J.N. (eds.) RAMICS 2015. LNCS, vol. 9348, pp. 326\u2013343. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-24704-5_20"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.jlamp.2017.03.004","volume":"89","author":"N Krivulin","year":"2017","unstructured":"Krivulin, N.: Algebraic solution of tropical optimization problems via matrix sparsification with application to scheduling. J. Log. Algebr. Methods Program. 89, 150\u2013170 (2017). https:\/\/doi.org\/10.1016\/j.jlamp.2017.03.004","journal-title":"J. Log. Algebr. Methods Program."},{"key":"12_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/978-3-319-57418-9_14","volume-title":"Relational and Algebraic Methods in Computer Science","author":"N Krivulin","year":"2017","unstructured":"Krivulin, N.: Complete solution of an optimization problem in tropical semifield. In: H\u00f6fner, P., Pous, D., Struth, G. (eds.) RAMICS 2017. LNCS, vol. 10226, pp. 226\u2013241. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57418-9_14"},{"key":"12_CR25","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.jlamp.2018.05.002","volume":"99","author":"N Krivulin","year":"2018","unstructured":"Krivulin, N.: Complete algebraic solution of multidimensional optimization problems in tropical semifield. J. Log. Algebr. Methods Program. 99, 26\u201340 (2018). https:\/\/doi.org\/10.1016\/j.jlamp.2018.05.002","journal-title":"J. Log. Algebr. Methods Program."},{"key":"12_CR26","doi-asserted-by":"publisher","unstructured":"Krivulin, N.: Complete solution of tropical vector inequalities using matrix sparsification. Appl. Math. 65(6), 755\u2013775 (2020). https:\/\/doi.org\/10.21136\/AM.2020.0376-19","DOI":"10.21136\/AM.2020.0376-19"},{"issue":"4","key":"12_CR27","doi-asserted-by":"publisher","first-page":"884","DOI":"10.1016\/j.laa.2011.02.014","volume":"435","author":"E Lorenzo","year":"2011","unstructured":"Lorenzo, E., de la Puente, M.J.: An algorithm to describe the solution set of any tropical linear system $${A}\\odot x={B}\\odot x$$. Linear Algebra Appl. 435(4), 884\u2013901 (2011). https:\/\/doi.org\/10.1016\/j.laa.2011.02.014","journal-title":"Linear Algebra Appl."},{"key":"12_CR28","doi-asserted-by":"publisher","unstructured":"Maclagan, D., Sturmfels, B.: Introduction to Tropical Geometry, Graduate Studies in Mathematics, vol.\u00a0161. AMS, Providence, RI (2015). https:\/\/doi.org\/10.1090\/gsm\/161","DOI":"10.1090\/gsm\/161"},{"key":"12_CR29","doi-asserted-by":"publisher","unstructured":"Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009). https:\/\/doi.org\/10.1017\/CBO9781139195218","DOI":"10.1017\/CBO9781139195218"},{"issue":"2","key":"12_CR30","first-page":"313","volume":"51","author":"L Truffet","year":"2010","unstructured":"Truffet, L.: A decomposition formula of idempotent polyhedral cones based on idempotent superharmonic spaces. Beitr. Algebra Geom. 51(2), 313\u2013336 (2010)","journal-title":"Beitr. Algebra Geom."},{"key":"12_CR31","doi-asserted-by":"publisher","unstructured":"Walkup, E.A., Borriello, G., Taylor, J.M., Atiyah, M.: A general linear max-plus solution technique. In: Gunawardena, J. (ed.) Idempotency, p. 406-415. Publications of the Newton Institute, Cambridge Univ. Press (1998). https:\/\/doi.org\/10.1017\/CBO9780511662508.024","DOI":"10.1017\/CBO9780511662508.024"},{"key":"12_CR32","unstructured":"Zimmermann, K.: A general separation theorem in extremal algebras. Ekonom.-Mat. Obzor 13(2), 179-201 (1977)"}],"container-title":["Lecture Notes in Computer Science","Relational and Algebraic Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-68279-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,11]],"date-time":"2024-08-11T23:08:08Z","timestamp":1723417688000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-68279-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031682780","9783031682797"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-68279-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"12 August 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RAMiCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Relational and Algebraic Methods in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ramics2023a","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ramics-conf.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}