{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,15]],"date-time":"2024-02-15T21:42:28Z","timestamp":1708033348249},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,3,16]],"date-time":"2012-03-16T00:00:00Z","timestamp":1331856000000},"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":[[2013,6]]},"DOI":"10.1007\/s00453-012-9640-8","type":"journal-article","created":{"date-parts":[[2012,3,15]],"date-time":"2012-03-15T15:59:47Z","timestamp":1331827187000},"page":"346-368","source":"Crossref","is-referenced-by-count":6,"title":["Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation"],"prefix":"10.1007","volume":"66","author":[{"given":"Satoru","family":"Iwata","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mizuyo","family":"Takamatsu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,3,16]]},"reference":[{"key":"9640_CR1","first-page":"565","volume":"22","author":"E.H. Bareiss","year":"1968","unstructured":"Bareiss, E.H.: Sylvester\u2019s identity and multistep integer-preserving Gaussian elimination. Math. Comput. 22, 565\u2013578 (1968)","journal-title":"Math. Comput."},{"key":"9640_CR2","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1093\/imamat\/10.1.68","volume":"10","author":"E.H. Bareiss","year":"1972","unstructured":"Bareiss, E.H.: Computational solutions of matrix problems over an integral domain. IMA J. Appl. Math. 10, 68\u2013104 (1972)","journal-title":"IMA J. Appl. Math."},{"key":"9640_CR3","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1007\/BF01178683","volume":"28","author":"D.G. Cantor","year":"1991","unstructured":"Cantor, D.G., Kaltofen, E.: On fast multiplication of polynomials over arbitrary algebras. Acta Inform. 28, 693\u2013701 (1991)","journal-title":"Acta Inform."},{"key":"9640_CR4","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1137\/0609010","volume":"9","author":"J. Demmel","year":"1988","unstructured":"Demmel, J., K\u00e5gstr\u00f6m, B.: Accurate solutions of ill-posed problems in control theory. SIAM J. Matrix Anal. Appl. 9, 126\u2013145 (1988)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9640_CR5","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0001-8708(92)90028-J","volume":"93","author":"A.W.M. Dress","year":"1992","unstructured":"Dress, A.W.M., Wenzel, W.: Valuated matroids. Adv. Math. 93, 214\u2013250 (1992)","journal-title":"Adv. Math."},{"key":"9640_CR6","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/jcss.1996.0054","volume":"53","author":"H.N. Gabow","year":"1996","unstructured":"Gabow, H.N., Xu, Y.: Efficient theoretic and practical algorithms for linear matroid intersection problems. J. Comput. Syst. Sci. 53, 129\u2013147 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"9640_CR7","volume-title":"The Theory of Matrices","author":"F.R. Gantmacher","year":"1959","unstructured":"Gantmacher, F.R.: The Theory of Matrices. Chelsea, New York (1959)"},{"key":"9640_CR8","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1137\/070684008","volume":"39","author":"N.J.A. Harvey","year":"2009","unstructured":"Harvey, N.J.A.: Algebraic algorithms for matching and matroid problems. SIAM J. Comput. 39, 679\u2013702 (2009)","journal-title":"SIAM J. Comput."},{"key":"9640_CR9","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s00453-003-1022-9","volume":"36","author":"S. Iwata","year":"2003","unstructured":"Iwata, S.: Computing the maximum degree of minors in matrix pencils via combinatorial relaxation. Algorithmica 36, 331\u2013341 (2003)","journal-title":"Algorithmica"},{"key":"9640_CR10","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/PL00011427","volume":"90","author":"S. Iwata","year":"2001","unstructured":"Iwata, S., Murota, K.: Combinatorial relaxation algorithm for mixed polynomial matrices. Math. Program. 90, 353\u2013371 (2001)","journal-title":"Math. Program."},{"key":"9640_CR11","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1137\/0917064","volume":"17","author":"S. Iwata","year":"1996","unstructured":"Iwata, S., Murota, K., Sakuta, I.: Primal-dual combinatorial relaxation algorithms for the maximum degree of subdeterminants. SIAM J. Sci. Comput. 17, 993\u20131012 (1996)","journal-title":"SIAM J. Sci. Comput."},{"key":"9640_CR12","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1137\/100783315","volume":"32","author":"S. Iwata","year":"2011","unstructured":"Iwata, S., Takamatsu, M.: On the Kronecker canonical form of mixed matrix pencils. SIAM J. Matrix Anal. Appl. 32, 44\u201371 (2011)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9640_CR13","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1109\/FOCS.2004.40","volume-title":"45th Annual IEEE Symposium on Foundations of Computer Science","author":"M. Mucha","year":"2004","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 248\u2013255. IEEE Comput. Soc., Los Alamitos (2004)"},{"key":"9640_CR14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00453-005-1187-5","volume":"45","author":"M. Mucha","year":"2006","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings in planar graphs via Gaussian elimination. Algorithmica 45, 3\u201320 (2006)","journal-title":"Algorithmica"},{"key":"9640_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61586-3","volume-title":"Systems Analysis by Graphs and Matroids\u2014Structural Solvability and Controllability","author":"K. Murota","year":"1987","unstructured":"Murota, K.: Systems Analysis by Graphs and Matroids\u2014Structural Solvability and Controllability. Springer, Berlin (1987)"},{"key":"9640_CR16","doi-asserted-by":"crossref","first-page":"1132","DOI":"10.1137\/0219077","volume":"19","author":"K. Murota","year":"1990","unstructured":"Murota, K.: Computing Puiseux-series solutions to determinantal equations via combinatorial relaxation. SIAM J. Comput. 19, 1132\u20131161 (1990)","journal-title":"SIAM J. Comput."},{"key":"9640_CR17","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF01235719","volume":"6","author":"K. Murota","year":"1995","unstructured":"Murota, K.: Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form. Appl. Algebra Eng. Commun. Comput. 6, 251\u2013273 (1995)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"9640_CR18","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1137\/S0097539791201897","volume":"24","author":"K. Murota","year":"1995","unstructured":"Murota, K.: Computing the degree of determinants via combinatorial relaxation. SIAM J. Comput. 24, 765\u2013796 (1995)","journal-title":"SIAM J. Comput."},{"key":"9640_CR19","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/S0895480195279994","volume":"9","author":"K. Murota","year":"1996","unstructured":"Murota, K.: Valuated matroid intersection, I: Optimality criteria. SIAM J. Discrete Math. 9, 545\u2013561 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"9640_CR20","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1137\/S0895480195280009","volume":"9","author":"K. Murota","year":"1996","unstructured":"Murota, K.: Valuated matroid intersection, II: Algorithms. SIAM J. Discrete Math. 9, 562\u2013576 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"9640_CR21","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/S0895479896311438","volume":"20","author":"K. Murota","year":"1999","unstructured":"Murota, K.: On the degree of mixed polynomial matrices. SIAM J. Matrix Anal. Appl. 20, 196\u2013227 (1999)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9640_CR22","volume-title":"Matrices and Matroids for Systems Analysis","author":"K. Murota","year":"2000","unstructured":"Murota, K.: Matrices and Matroids for Systems Analysis. Springer, Berlin (2000)"},{"key":"9640_CR23","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF03167048","volume":"2","author":"K. Murota","year":"1985","unstructured":"Murota, K., Iri, M.: Structural solvability of systems of equations\u2014A mathematical formulation for distinguishing accurate and inaccurate numbers in structural analysis of systems. Jpn. J. Appl. Math. 2, 247\u2013271 (1985)","journal-title":"Jpn. J. Appl. Math."},{"key":"9640_CR24","doi-asserted-by":"crossref","first-page":"4480","DOI":"10.1016\/j.tcs.2009.07.028","volume":"410","author":"P. Sankowski","year":"2009","unstructured":"Sankowski, P.: Maximum weight bipartite matching in matrix multiplication time. Theor. Comput. Sci. 410, 4480\u20134488 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9640_CR25","unstructured":"Storjohann, A.: Algorithms for matrix canonical forms. Ph.D. thesis, ETH Z\u00fcrich (2000)"},{"key":"9640_CR26","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1080\/00207177308932538","volume":"18","author":"J.S. Thorp","year":"1973","unstructured":"Thorp, J.S.: The singular pencil of a linear dynamical system. Int. J. Control 18, 577\u2013596 (1973)","journal-title":"Int. J. Control"},{"key":"9640_CR27","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1109\/TAC.1981.1102593","volume":"AC-26","author":"G.C. Verghese","year":"1981","unstructured":"Verghese, G.C., Kailath, T.: Rational matrix structure. IEEE Trans. Autom. Control AC-26, 434\u2013439 (1981)","journal-title":"IEEE Trans. Autom. Control"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9640-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9640-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9640-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:09Z","timestamp":1559137509000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9640-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,16]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["9640"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9640-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,16]]}}}