{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T17:32:23Z","timestamp":1649093543914},"reference-count":49,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1987,5,1]],"date-time":"1987-05-01T00:00:00Z","timestamp":546825600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":9574,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[1987,5]]},"DOI":"10.1016\/0166-218x(87)90004-7","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T23:43:01Z","timestamp":1027640581000},"page":"17-27","source":"Crossref","is-referenced-by-count":1,"title":["A very personal reminiscence on the problem of computational complexity"],"prefix":"10.1016","volume":"17","author":[{"given":"Masao","family":"Iri","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0166-218X(87)90004-7_BIB1","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/0166-218X(87)90004-7_BIB2","first-page":"827","article-title":"Incidence matrices and linear graphs","volume":"8","author":"Auslander","year":"1959","journal-title":"J. Mathematics and Mechanics"},{"key":"10.1016\/0166-218X(87)90004-7_BIB3","first-page":"7","article-title":"O vychislenii znacheni\u01d0 mnogchlenov ot odnogo peremennogo s predvaritel'noi obrabotko\u01d0 ko\u00e8ffitsientov","volume":"5","author":"Belaga","year":"1961","journal-title":"Problemy Kibernetiki"},{"key":"10.1016\/0166-218X(87)90004-7_BIB4","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1109\/TCT.1961.1086796","article-title":"Conditions for the realizability of a conductance matrix","volume":"8","author":"Biorci","year":"1961","journal-title":"IRE Trans. Circuit Theory"},{"key":"10.1016\/0166-218X(87)90004-7_BIB5","first-page":"1","article-title":"A structure theory of bipartite graphs of finite exterior dimension","volume":"53","author":"Dulmage","year":"1959","journal-title":"Trans. Roy. Soc. Canada"},{"key":"10.1016\/0166-218X(87)90004-7_BIB6","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","article-title":"Theoretical improvements in algorithmic efficiency for network flow problems","volume":"19","author":"Edmonds","year":"1972","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0166-218X(87)90004-7_BIB7","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1002\/sapm1958371193","article-title":"Graphs and vector spaces","volume":"37","author":"Gould","year":"1958","journal-title":"J. Mathematics and Physics"},{"key":"10.1016\/0166-218X(87)90004-7_BIB8","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1109\/TCT.1959.1086602","article-title":"How to grow your own tree from given cut\u2013set or tie\u2013set matrices","volume":"6","author":"Guillemin","year":"1959","journal-title":"IRE Trans. Circuit Theory"},{"key":"10.1016\/0166-218X(87)90004-7_BIB9","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1147\/rd.164.0412","article-title":"Finding all shortest distances in a directed network","volume":"16","author":"Hoffman","year":"1972","journal-title":"IBM J. Research and Development"},{"key":"10.1016\/0166-218X(87)90004-7_BIB10","series-title":"Proc. IFIP Congress","first-page":"18","article-title":"Planarity testing in V log V steps","author":"Hopcroft","year":"1971"},{"key":"10.1016\/0166-218X(87)90004-7_BIB11","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","article-title":"Efficient planarity testing","volume":"21","author":"Hopcroft","year":"1974","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0166-218X(87)90004-7_BIB12","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1147\/rd.134.0387","article-title":"Shortcut in the decomposition algorithm for shortest paths in a network","volume":"13","author":"Hu","year":"1969","journal-title":"IBM J. Research and Development"},{"key":"10.1016\/0166-218X(87)90004-7_BIB13","series-title":"Master's Thesis","article-title":"Studies of the amounts of labour of algorithms )","author":"Ikura","year":"1967"},{"key":"10.1016\/0166-218X(87)90004-7_BIB14","unstructured":"M. Iri, A necessary and sufficient condition for the existence of a network which has a given matrix as its loop (cut-set) matrix (in Japanese), Proc. 1961 National Conf. of the Institute of Electrical Communication Engineers of Japan, No. 23."},{"key":"10.1016\/0166-218X(87)90004-7_BIB15","article-title":"A necessary and sufficient condition for a matrix to be the loop or cut\u2013set matrix of a graph and a practical method for the topological synthesis of networks","author":"Iri","year":"1962","journal-title":"RAAG Research Notes"},{"key":"10.1016\/0166-218X(87)90004-7_BIB16","first-page":"41","article-title":"Application of graph theory to switching networks \u2014 Fundamental problem and its solution, Progress in Radio Science 1960\u20131963","volume":"Vol. 6","author":"Iri","year":"1963"},{"key":"10.1016\/0166-218X(87)90004-7_BIB17","article-title":"A system of programmes for topological synthesis of networks","author":"Iri","year":"1964","journal-title":"International Conf. on Microwaves, Circuit Theory and Information Theory"},{"issue":"A-XIII","key":"10.1016\/0166-218X(87)90004-7_BIB18","first-page":"4","article-title":"On the synthesis of loop and cutset matrices and the related problems","volume":"Vol. 4","author":"Iri","year":"1968","journal-title":"RAAG Memories"},{"key":"10.1016\/0166-218X(87)90004-7_BIB19","series-title":"Network Flow, Transportation and Scheduling \u2014 Theory and Algorithms","author":"Iri","year":"1969"},{"key":"10.1016\/0166-218X(87)90004-7_BIB20","unstructured":"M. Iri, On the amount of labour in linear computation (in Japanese), Paper presented at the meeting on January 8, 1970, of the Computer Programming Study Group of the JUSE."},{"key":"10.1016\/0166-218X(87)90004-7_BIB21","first-page":"21","article-title":"On algorithms in numerical computation","author":"Iri","year":"1970","journal-title":"S\u016bri-Kagaku (Mathematical Sciences)"},{"key":"10.1016\/0166-218X(87)90004-7_BIB22","unstructured":"M. Iri, On the techniques for processing informations with graphical structures (in Japanese), Proc. 1972 Joint Conf. of the Four Electrical Societies of Japan, No. 217."},{"key":"10.1016\/0166-218X(87)90004-7_BIB23","article-title":"Path-sets, operator semigroups and shortest-path algorithms on a network","author":"Iri","year":"1972","journal-title":"RAAG Research Notes"},{"key":"10.1016\/0166-218X(87)90004-7_BIB24","series-title":"Proc. IFIP Congress 1971","first-page":"1150","article-title":"The graphical techniques used for a chemical process simulator \u201cJUSE GIFS\u201d","author":"Iri","year":"1972"},{"issue":"1","key":"10.1016\/0166-218X(87)90004-7_BIB25","first-page":"21","article-title":"O minimizatsii chisla arifmeticheskikh operatsi\u01d0 pri reshenii lineinykh algebraicheskikh sistem uravneni\u01d0","volume":"5","author":"Klyuev","year":"1965","journal-title":"Zhurnal Vychislitel'no\u01d0 Matematiki i Matematichesko\u01d0 Fiziki"},{"issue":"1","key":"10.1016\/0166-218X(87)90004-7_BIB26","first-page":"3","article-title":"O minimizatsii vychislichel'nykh algoritmov pri nekotorykh preobrazovaniyakh matrits","volume":"7","author":"Klyuev","year":"1967","journal-title":"Zhurnal Vychislitel'no\u01d0 Matematiki i Matematichesko\u01d0 Fiziki"},{"key":"10.1016\/0166-218X(87)90004-7_BIB27","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF01438261","article-title":"Base tensorielle des matrices de Hankel (ou de Toeplitz) \u2014 Applications","volume":"23","author":"Lafon","year":"1975","journal-title":"Numerische Mathematik"},{"key":"10.1016\/0166-218X(87)90004-7_BIB28","series-title":"Theory of Graphs","first-page":"215","article-title":"An algorithm for planarity testing of graphs","author":"Lempel","year":"1967"},{"key":"10.1016\/0166-218X(87)90004-7_BIB29","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1109\/TCT.1959.1086609","article-title":"Irredundant and redundant Boolean branch\u2013networks","volume":"6","author":"L\u00f6fgren","year":"1959","journal-title":"IRE Trans. Circuit Theory"},{"key":"10.1016\/0166-218X(87)90004-7_BIB30","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1147\/rd.43.0321","article-title":"Synthesis of switching functions by linear graph theory","volume":"4","author":"Mayeda","year":"1960","journal-title":"IBM J. Research and Development"},{"key":"10.1016\/0166-218X(87)90004-7_BIB31","first-page":"201","article-title":"A note on the optimality of some all-shortest-path algorithms","volume":"15","author":"Nakamori","year":"1972","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"10.1016\/0166-218X(87)90004-7_BIB32","first-page":"120","article-title":"Realization of Boolean polynomials based on incidence matrices","author":"Okada","year":"1959","journal-title":"Proc. 9th Eastern Joint Computer Conference"},{"key":"10.1016\/0166-218X(87)90004-7_BIB33","article-title":"Developing methods for estimating traffic volumes","year":"1972","journal-title":"Technical Report"},{"key":"10.1016\/0166-218X(87)90004-7_BIB34","article-title":"Fundamental studies of the techniques for processing network problems in operations research by computers","year":"1973","journal-title":"Technical Report Series T-73-1"},{"key":"10.1016\/0166-218X(87)90004-7_BIB35","article-title":"Estimation of traffic volumes on expressways by means of new methods","year":"1973","journal-title":"Technical Report Series T-73-2"},{"key":"10.1016\/0166-218X(87)90004-7_BIB36","first-page":"17","article-title":"Nekotorye skhemy dlya vychisleniya znacheni\u01d0 polinomov s veshchestvennymi ko\u00e8ffitsientami","volume":"5","author":"Pan","year":"1961","journal-title":"Problemy Kibernetiki"},{"issue":"1","key":"10.1016\/0166-218X(87)90004-7_BIB37","first-page":"103","article-title":"O sposobakh Vychisleniya znacheni\u01d0 mnogochlenov","volume":"21","author":"Pan","year":"1966","journal-title":"Uspekhi Matematicheskikh Nauk"},{"key":"10.1016\/0166-218X(87)90004-7_BIB38","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","article-title":"Gaussian elimination is not optimal","volume":"13","author":"Strassen","year":"1969","journal-title":"Numerische Mathematik"},{"key":"10.1016\/0166-218X(87)90004-7_BIB39","first-page":"184","article-title":"Vermeidung von Divisionen","volume":"264","author":"Strassen","year":"1973","journal-title":"Crelle J. Reine Angew. Math."},{"key":"10.1016\/0166-218X(87)90004-7_BIB40","series-title":"STAN-CS-244-71","article-title":"An efficient planarity algorithm","author":"Tarjan","year":"1971"},{"key":"10.1016\/0166-218X(87)90004-7_BIB41","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1002\/net.3230010206","article-title":"On some techniques useful for solution of transportation network problems","volume":"1","author":"Tomizawa","year":"1971","journal-title":"Networks"},{"key":"10.1016\/0166-218X(87)90004-7_BIB42","series-title":"Paper of the Technical Group on Circuit and System Theory","article-title":"An O(m3) algorithm for solving the realization problem of graphs","author":"Tomizawa","year":"1976"},{"key":"10.1016\/0166-218X(87)90004-7_BIB43","series-title":"Programming techniques in FORTRAN for information engineers","author":"Tsunekawa","year":"1970"},{"key":"10.1016\/0166-218X(87)90004-7_BIB44","first-page":"905","article-title":"An algorithm for determining whether a given binary matroid is graphic","volume":"11","author":"Tutte","year":"1960","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/0166-218X(87)90004-7_BIB45","doi-asserted-by":"crossref","first-page":"108","DOI":"10.4153\/CJM-1964-011-0","article-title":"From matrices to graphs","volume":"16","author":"Tutte","year":"1964","journal-title":"Canad. J. Math."},{"key":"10.1016\/0166-218X(87)90004-7_BIB46","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1109\/TC.1968.227420","article-title":"A new algorithm for inner product","volume":"17","author":"Winograd","year":"1968","journal-title":"IEEE Trans. Computers"},{"key":"10.1016\/0166-218X(87)90004-7_BIB47","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1002\/cpa.3160230204","article-title":"On the number of multiplications necessary to compute certain functions","volume":"23","author":"Winograd","year":"1970","journal-title":"Comm. Pure App. Math."},{"key":"10.1016\/0166-218X(87)90004-7_BIB48","series-title":"Paper of the Technical Group on Circuit Theory","article-title":"A method of synthesis of N-port G-graphs with N + 1 nodes","author":"Yasuda","year":"1963"},{"key":"10.1016\/0166-218X(87)90004-7_BIB49","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1287\/opre.19.4.983","article-title":"On Hu's decomposition algorithm for shortest paths in a network","volume":"19","author":"Yen","year":"1971","journal-title":"Operations Research"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X87900047?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X87900047?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T01:53:15Z","timestamp":1555120395000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0166218X87900047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,5]]},"references-count":49,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1987,5]]}},"alternative-id":["0166218X87900047"],"URL":"https:\/\/doi.org\/10.1016\/0166-218x(87)90004-7","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[1987,5]]}}}