{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T20:08:32Z","timestamp":1790539712202,"version":"4.1.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1997,8,1]],"date-time":"1997-08-01T00:00:00Z","timestamp":870393600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1997,8]]},"DOI":"10.1007\/bf02614369","type":"journal-article","created":{"date-parts":[[2007,4,28]],"date-time":"2007-04-28T04:34:50Z","timestamp":1177734890000},"page":"169-177","source":"Crossref","is-referenced-by-count":58,"title":["Dynamic trees as search trees via euler tours, applied to the network simplex algorithm"],"prefix":"10.1007","volume":"78","author":[{"given":"Robert E.","family":"Tarjan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF02614369_CR1","first-page":"1259","volume":"3","author":"G.M. Adel\u2019son-Vel\u2019skii","year":"1962","unstructured":"G.M. Adel\u2019son-Vel\u2019skii and E.M. Landis, An algorithm for the organization of information,Soviet Math. Dokl. 3 (1962) 1259\u20131262.","journal-title":"Soviet Math. Dokl."},{"key":"BF02614369_CR2","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"R. Bayer and E. McCreight, Organization of large ordered indexes,Acta Inform. 1 (1972) 173\u2013189.","journal-title":"Acta Inform"},{"key":"BF02614369_CR3","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"S. Bent","year":"1985","unstructured":"S. Bent, D. Sleator and R.E. Tarjan, Biased search trees,SIAM J. Computing 14 (1985) 545\u2013568.","journal-title":"SIAM J. Computing"},{"key":"BF02614369_CR4","unstructured":"R.F. Cohen and R. Tamassia, Dynamic expression trees and their applications,Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms (1991) 52\u201361."},{"key":"BF02614369_CR5","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"J. Edmonds and R.M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems,J. Assoc. Comput. Mach. 19 (1972) 248\u2013264.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02614369_CR6","unstructured":"D. Eppstein, G.F. Italiano, R. Tamassia, R.E. Tarjan, J. Westbrook and M. Yung, Maintenance of a minimum spanning forest in a dynamic planar graph,Proc. 1st ACM-SIAM Symp. on Discrete Algorithms (1990) 1\u201311."},{"key":"BF02614369_CR7","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G.N. Frederickson","year":"1985","unstructured":"G.N. Frederickson, Data structures for on-line updating of minimum spanning trees,SIAM J. Comput. 14 (1985) 781\u2013798.","journal-title":"SIAM J. Comput."},{"key":"BF02614369_CR8","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson, Ambivalent data structures for dynamic 2-edge-connectivity andk smallest spanning trees,Proc. 32nd IEEE Symp. on Foundations of Computer Science (1991) 632\u2013641.","DOI":"10.1109\/SFCS.1991.185429"},{"key":"BF02614369_CR9","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H.N. Gabow","year":"1986","unstructured":"H.N. Gabow, Z. Galil, T. Spencer and R.E. Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs,Combinatorica 6 (1986) 109\u2013122.","journal-title":"Combinatorica"},{"key":"BF02614369_CR10","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF01594940","volume":"50","author":"A.V. Goldberg","year":"1991","unstructured":"A.V. Goldberg, M.D. Grigoriadis, and R.E. Tarjan, Use of dynamic trees in a network simplex algorithm for the maximum flow problems,Math. Prog. 50 (1991) 277\u2013290.","journal-title":"Math. Prog."},{"key":"BF02614369_CR11","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A.V. Goldberg","year":"1988","unstructured":"A.V. Goldberg and R.E. Tarjan, A new approach to the maximum flow problem,J. Assoc. Comput. Mach. 35 (1988) 921\u2013940.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02614369_CR12","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1145\/76359.76368","volume":"36","author":"A.V. Goldberg","year":"1989","unstructured":"A.V. Goldberg and R.E. Tarjan, Finding minimum-cost circulations by canceling negative cycles,J. Assoc. Comput. Mach. 36 (1989) 873\u2013886.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02614369_CR13","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1287\/moor.15.3.430","volume":"15","author":"A.V. Goldberg","year":"1990","unstructured":"A.V. Goldberg and R.E. Tarjan, Finding minimum-cost circulations by successive approximation,Math. of Oper. Res. 15 (1990) 430\u2013466.","journal-title":"Math. of Oper. Res."},{"key":"BF02614369_CR14","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF01580869","volume":"47","author":"D. Goldfarb","year":"1990","unstructured":"D. Goldfarb and J. Hao, A primal simplex algorithm that solves the maximum flow problem in at mostnm pivots and O(n 2m) time,Mathematical Programming 47 (1990) 353\u2013365.","journal-title":"Mathematical Programming"},{"key":"BF02614369_CR15","doi-asserted-by":"crossref","unstructured":"L.J. Guibas and R. Sedgewick, A dichromatic framework for balanced trees,Proc. 19th Annual IEEE Symposium on Foundations of Computer Science (1978) 8\u201321.","DOI":"10.1109\/SFCS.1978.3"},{"key":"BF02614369_CR16","doi-asserted-by":"crossref","unstructured":"M.R. Henzinger and V. King, Randomized dynamic graph algorithms with polylogarithmic time per operation,Proc. 27th Annual ACM Symp. on Theory of Computing (1995) 519\u2013527.","DOI":"10.1145\/225058.225269"},{"key":"BF02614369_CR17","doi-asserted-by":"crossref","unstructured":"G.L. Miller and J.H. Reif, Parallel tree contraction and its application,Proc. 26th Annual IEEE Symp. on Foundations of Comp. Sci. (1985) 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"key":"BF02614369_CR18","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0304-3975(94)90159-7","volume":"130","author":"P.B. Miltersen","year":"1994","unstructured":"P.B. Miltersen, S. Subramanian, J.S. Vitter and R. Tamassia, Complexity models for incremental computation,Theoretical Computer Science 130 (1994) 203\u2013236.","journal-title":"Theoretical Computer Science"},{"key":"BF02614369_CR19","unstructured":"J.B. Orlin, A polynomial time primal network simplex algorithm for minimum cost flows (an extended abstract),Proc. 7th ACM-SIAM Symp. on Discrete Algorithms (1996) 474\u2013481."},{"key":"BF02614369_CR20","first-page":"109","volume":"78","author":"J.B. Orlin","year":"1997","unstructured":"J.B. Orlin, A polynomial time primal network simplex algorithm for minimum cost flows,Mathematical Programming 78 (1997) 109\u2013129.","journal-title":"Mathematical Programming"},{"key":"BF02614369_CR21","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. Sleator","year":"1983","unstructured":"D. Sleator and R.E. Tarjan, A data structure for dynamic trees,J. Computer and System Sciences 26 (1983) 362\u2013391.","journal-title":"J. Computer and System Sciences"},{"key":"BF02614369_CR22","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. Sleator","year":"1985","unstructured":"D. Sleator and R.E. Tarjan, Self-adjusting binary search trees,J. Assoc. Comput. Mach. 32 (1985) 652\u2013686.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02614369_CR23","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1287\/moor.16.2.272","volume":"16","author":"R.E. Tarjan","year":"1991","unstructured":"R.E. Tarjan, Efficiency of the primal network simplex algorithm for the minimum-cost circulation problem,Math. of Oper. Res. 16 (1991) 272\u2013291.","journal-title":"Math. of Oper. Res."},{"key":"BF02614369_CR24","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0020-0190(83)90099-6","volume":"16","author":"R.E. Tarjan","year":"1983","unstructured":"R.E. Tarjan, Updating a balanced search tree in O(1) rotations,Information Processing Letters 16 (1983) 253\u2013257.","journal-title":"Information Processing Letters"},{"key":"BF02614369_CR25","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms,CBMS 44","author":"R.E. Tarjan","year":"1983","unstructured":"R.E. Tarjan, Data Structures and Network Algorithms,CBMS 44, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983."},{"key":"BF02614369_CR26","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R.E. Tarjan","year":"1985","unstructured":"R.E. Tarjan and U. Vishkin, An efficient parallel biconnectivity algorithm,SIAM J. Comput. 14 (1985) 862\u2013874.","journal-title":"SIAM J. Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614369.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02614369\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614369","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T23:19:20Z","timestamp":1736983160000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02614369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,8]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,8]]}},"alternative-id":["BF02614369"],"URL":"https:\/\/doi.org\/10.1007\/bf02614369","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,8]]}}}