{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:40:37Z","timestamp":1725586837675},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208065"},{"type":"electronic","value":"9783642208072"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20807-2_22","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T13:58:49Z","timestamp":1308405529000},"page":"274-286","source":"Crossref","is-referenced-by-count":1,"title":["Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation"],"prefix":"10.1007","author":[{"given":"Satoru","family":"Iwata","sequence":"first","affiliation":[]},{"given":"Mizuyo","family":"Takamatsu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_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. Mathematics of Computation\u00a022, 565\u2013578 (1968)","journal-title":"Mathematics of Computation"},{"key":"22_CR2","doi-asserted-by":"publisher","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 Journal of Applied Mathematics\u00a010, 68\u2013104 (1972)","journal-title":"IMA Journal of Applied Mathematics"},{"key":"22_CR3","doi-asserted-by":"publisher","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 Informatica\u00a028, 693\u2013701 (1991)","journal-title":"Acta Informatica"},{"key":"22_CR4","doi-asserted-by":"publisher","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. Advances in Mathematics\u00a093, 214\u2013250 (1992)","journal-title":"Advances in Mathematics"},{"key":"22_CR5","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":"22_CR6","doi-asserted-by":"publisher","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 Journal on Computing\u00a039, 679\u2013702 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR7","doi-asserted-by":"publisher","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\u00a036, 331\u2013341 (2003)","journal-title":"Algorithmica"},{"key":"22_CR8","doi-asserted-by":"publisher","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. Mathematical Programming\u00a090, 353\u2013371 (2001)","journal-title":"Mathematical Programming"},{"key":"22_CR9","doi-asserted-by":"publisher","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 Journal on Scientific Computing\u00a017, 993\u20131012 (1996)","journal-title":"SIAM Journal on Scientific Computing"},{"key":"22_CR10","doi-asserted-by":"publisher","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 Journal on Matrix Analysis and Applications\u00a032, 44\u201371 (2011)","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"22_CR11","doi-asserted-by":"publisher","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 Computer Society, Los Alamitos (2004)"},{"key":"22_CR12","doi-asserted-by":"publisher","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\u00a045, 3\u201320 (2006)","journal-title":"Algorithmica"},{"key":"22_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61586-3","volume-title":"Systems Analysis by Graphs and Matroids \u2014 Structural Solvability and Controllability","author":"K. Murota","year":"1987","unstructured":"Murota, K.: Systems Analysis by Graphs and Matroids \u2014 Structural Solvability and Controllability. Springer, Berlin (1987)"},{"key":"22_CR14","doi-asserted-by":"publisher","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 Journal on Computing\u00a019, 1132\u20131161 (1990)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR15","doi-asserted-by":"publisher","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. Applicable Algebra in Engineering, Communication and Computing\u00a06, 251\u2013273 (1995)","journal-title":"Applicable Algebra in Engineering, Communication and Computing"},{"key":"22_CR16","doi-asserted-by":"publisher","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 Journal on Computing\u00a024, 765\u2013796 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/S0895480195279994","volume":"9","author":"K. Murota","year":"1996","unstructured":"Murota, K.: Valuated matroid intersection, I: Optimality criteria. SIAM Journal on Discrete Mathematics\u00a09, 545\u2013561 (1996)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1137\/S0895480195280009","volume":"9","author":"K. Murota","year":"1996","unstructured":"Murota, K.: Valuated matroid intersection, II: Algorithms. SIAM Journal on Discrete Mathematics\u00a09, 562\u2013576 (1996)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"22_CR19","doi-asserted-by":"publisher","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 Journal on Matrix Analysis and Applications\u00a020, 196\u2013227 (1999)","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"22_CR20","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":"22_CR21","doi-asserted-by":"publisher","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 \u2014 A mathematical formulation for distinguishing accurate and inaccurate numbers in structural analysis of systems. Japan Journal of Applied Mathematics\u00a02, 247\u2013271 (1985)","journal-title":"Japan Journal of Applied Mathematics"},{"key":"22_CR22","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0410, 4480\u20134488 (2009)","journal-title":"Theoretical Computer Science"},{"unstructured":"Storjohann, A.: Algorithms for Matrix Canonical Forms. Ph.D. thesis, ETH Z\u00fcrich (2000)","key":"22_CR23"},{"key":"22_CR24","doi-asserted-by":"publisher","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. International Journal of Control\u00a018, 577\u2013596 (1973)","journal-title":"International Journal of Control"},{"key":"22_CR25","doi-asserted-by":"publisher","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 Transactions on Automatic Control\u00a0AC-26, 434\u2013439 (1981)","journal-title":"IEEE Transactions on Automatic Control"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatoral Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20807-2_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T01:54:13Z","timestamp":1553824453000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20807-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208065","9783642208072"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20807-2_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}