Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDRobert E. Tarjan
Robert Endre Tarjan
Person information
- affiliation: Princeton University, Department of Computer Science, NJ, USA
- award (1986): Turing Award
- award (1999): Paris Kanellakis Award
- award (1984): Frederick W. Lanchester Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 2010
[b4]George Pólya, Robert Endre Tarjan, Donald R. Woods:
Notes on Introductory Combinatorics (reprint of the 1983 edition). Modern Birkhäuser Classics, Birkhäuser 2010, ISBN 978-0-8176-4952-4, pp. 1-190- 1983
- [b3]George Pólya, Robert Endre Tarjan, Donald R. Woods:
Notes on introductory combinatorics. Progress in computer science 4, Birkhäuser 1983, ISBN 978-3-7643-3170-2, pp. I-VIII, 1-160 - [b2]Robert Endre Tarjan:
Data structures and network algorithms. CBMS-NSF regional conference series in applied mathematics 44, SIAM 1983, ISBN 978-0-89871-187-5, pp. I-VII, 1-131 - 1971
- [b1]Robert E. Tarjan:
An efficient planarity algorithm. Stanford University, USA, 1971
Journal Articles
- 2022
- [j186]Sixue Cliff Liu
, Robert Endre Tarjan:
Simple Concurrent Connected Components Algorithms. ACM Trans. Parallel Comput. 9(2): 9:1-9:26 (2022) - 2021
- [j185]Siddhartha V. Jayanti, Robert E. Tarjan:
Concurrent disjoint set union. Distributed Comput. 34(6): 413-436 (2021) - [j184]Robert E. Tarjan, Caleb C. Levy, Stephen Timmel:
Zip Trees. ACM Trans. Algorithms 17(4): 34:1-34:12 (2021) - 2017
- [j183]Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Robert E. Tarjan:
Minimum-Cost Flows in Unit-Capacity Networks. Theory Comput. Syst. 61(4): 987-1010 (2017) - [j182]Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan, Uri Zwick:
Hollow Heaps. ACM Trans. Algorithms 13(3): 42:1-42:27 (2017) - 2016
- [j181]Mahdi Amani, Kevin A. Lai, Robert E. Tarjan:
Amortized rotation cost in AVL trees. Inf. Process. Lett. 116(5): 327-330 (2016) - [j180]Loukas Georgiadis, Robert E. Tarjan:
Dominator Tree Certification and Divergent Spanning Trees. ACM Trans. Algorithms 12(1): 11:1-11:42 (2016) - [j179]Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Robert E. Tarjan:
A New Approach to Incremental Cycle Detection and Related Problems. ACM Trans. Algorithms 12(2): 14:1-14:22 (2016) - [j178]Loukas Georgiadis, Robert E. Tarjan:
Addendum to "Dominator Tree Certification and Divergent Spanning Trees". ACM Trans. Algorithms 12(4): 56:1-56:3 (2016) - [j177]Siddhartha Sen, Robert E. Tarjan, David Hong Kyun Kim:
Deletion Without Rebalancing in Binary Search Trees. ACM Trans. Algorithms 12(4): 57:1-57:31 (2016) - 2015
- [j176]Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan:
Rank-Balanced Trees. ACM Trans. Algorithms 11(4): 30:1-30:26 (2015) - 2014
- [j175]Andrew V. Goldberg, Robert Endre Tarjan:
Efficient maximum flow algorithms. Commun. ACM 57(8): 82-89 (2014) - [j174]Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, Robert Endre Tarjan:
The CB tree: a practical concurrent self-adjusting search tree. Distributed Comput. 27(6): 393-417 (2014) - [j173]Wojciech Fraczak, Loukas Georgiadis, Andrew Miller, Robert Endre Tarjan:
Corrections to "Finding dominators via disjoint set union" [J. Discrete Algorithms 23 (2013) 2-20]. J. Discrete Algorithms 26: 106-110 (2014) - [j172]Siddhartha Sen, Robert Endre Tarjan:
Deletion without rebalancing in multiway search trees. ACM Trans. Database Syst. 39(1): 8:1-8:14 (2014) - 2013
- [j171]Wojciech Fraczak, Loukas Georgiadis, Andrew Miller, Robert Endre Tarjan:
Finding dominators via disjoint set union. J. Discrete Algorithms 23: 2-20 (2013) - [j170]Haim Kaplan, Robert Endre Tarjan, Uri Zwick:
Soft Heaps Simplified. SIAM J. Comput. 42(4): 1660-1673 (2013) - 2012
- [j169]Pankaj K. Agarwal, Lars Arge, Haim Kaplan, Eyal Molad, Robert Endre Tarjan, Ke Yi:
An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries. SIAM J. Comput. 41(1): 104-127 (2012) - [j168]Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan:
Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance. ACM Trans. Algorithms 8(1): 3:1-3:33 (2012) - 2011
- [j167]Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan:
Rank-Pairing Heaps. SIAM J. Comput. 40(6): 1463-1485 (2011) - [j166]Loukas Georgiadis, Haim Kaplan, Nira Shafrir, Robert Endre Tarjan, Renato Fonseca F. Werneck:
Data structures for mergeable trees. ACM Trans. Algorithms 7(2): 14:1-14:30 (2011) - 2010
- [j165]Julie Ward, Bin Zhang, Shailendra Jain, Chris Fry, Thomas Olavson, Holger Mishal, Jason Amaral, Dirk Beyer, Ann Brecht, Brian Cargille, Russ Chadinha, Kathy Chou, Gavin DeNyse, Qi Feng, Cookie Padovani, Sesh Raj, Kurt Sunderbruch, Robert Endre Tarjan, Krishna Venkatraman, Joseph Woods, Jing Zhou:
HP Transforms Product Portfolio Management with Operations Research. Interfaces 40(1): 17-32 (2010) - 2009
- [j164]Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert Endre Tarjan, Renato Fonseca F. Werneck:
Shortest-path feasibility algorithms: An experimental evaluation. ACM J. Exp. Algorithmics 14 (2009) - [j163]Robert Endre Tarjan, Renato Fonseca F. Werneck:
Dynamic trees in practice. ACM J. Exp. Algorithmics 14 (2009) - 2008
- [j162]Bernhard Haeupler, Robert Endre Tarjan:
Planarity Algorithms via PQ-Trees (Extended Abstract). Electron. Notes Discret. Math. 31: 143-149 (2008) - [j161]Nina Mishra, Robert Schreiber, Isabelle Stanton, Robert Endre Tarjan:
Finding Strongly Knit Clusters in Social Networks. Internet Math. 5(1): 155-174 (2008) - [j160]Bernhard Haeupler, Robert Endre Tarjan:
Finding a feasible flow in a strongly connected network. Oper. Res. Lett. 36(4): 397-398 (2008) - [j159]Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan, Anne Rogers, Robert Endre Tarjan, Jeffery R. Westbrook:
Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems. SIAM J. Comput. 38(4): 1533-1573 (2008) - [j158]Haim Kaplan, Robert Endre Tarjan:
Thin heaps, thick heaps. ACM Trans. Algorithms 4(1): 3:1-3:14 (2008) - 2007
- [j157]Kamalika Chaudhuri, Anshul Kothari, Rudi Pendavingh, Ram Swaminathan, Robert Endre Tarjan, Yunhong Zhou:
Server Allocation Algorithms for Tiered Systems. Algorithmica 48(2): 129-146 (2007) - 2006
- [j156]Loukas Georgiadis, Robert Endre Tarjan, Renato Fonseca F. Werneck:
Finding Dominators in Practice. J. Graph Algorithms Appl. 10(1): 69-94 (2006) - [j155]Ran Mendelson, Robert Endre Tarjan, Mikkel Thorup, Uri Zwick:
Melding priority queues. ACM Trans. Algorithms 2(4): 535-556 (2006) - 2003
- [j154]Gary William Flake, Robert Endre Tarjan, Kostas Tsioutsiouliklis:
Graph Clustering and Minimum Cut Trees. Internet Math. 1(4): 385-408 (2003) - 2001
- [j153]Harold N. Gabow, Haim Kaplan, Robert Endre Tarjan:
Unique Maximum Matching Algorithms. J. Algorithms 40(2): 159-183 (2001) - 2000
- [j152]Haim Kaplan, Chris Okasaki, Robert Endre Tarjan:
Simple Confluently Persistent Catenable Lists. SIAM J. Comput. 30(3): 965-977 (2000) - 1999
- [j151]Haim Kaplan, Ron Shamir, Robert Endre Tarjan:
Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs. SIAM J. Comput. 28(5): 1906-1922 (1999) - [j150]Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman:
Tight Analyses of Two Local Load Balancing Algorithms. SIAM J. Comput. 29(1): 29-64 (1999) - [j149]Haim Kaplan, Ron Shamir, Robert Endre Tarjan:
A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals. SIAM J. Comput. 29(3): 880-892 (1999) - 1998
- [j148]Lesley R. Matheson, Robert Endre Tarjan:
Culturally Induced Information Impactedness: A Prescription for Failure in Software Ventures. J. Manag. Inf. Syst. 15(2): 23-40 (1998) - 1997
- [j147]Brandon Dixon, Robert Endre Tarjan:
Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time. Algorithmica 17(1): 11-18 (1997) - [j146]Susan E. Dorward, Lesley R. Matheson, Robert Endre Tarjan:
Toward Efficient Unstructured Multigrid Preprocessing. Int. J. High Perform. Comput. Appl. 11(1): 12-33 (1997) - [j145]Robert Endre Tarjan:
Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math. Program. 77: 169-177 (1997) - 1996
- [j144]Lesley R. Matheson, Robert Endre Tarjan:
Dominating Sets in Planar Graphs. Eur. J. Comb. 17(6): 565-568 (1996) - [j143]Lesley R. Matheson, Robert Endre Tarjan:
Parallelism in multigrid methods: How much is too much? Int. J. Parallel Program. 24(5): 397-432 (1996) - [j142]Lesley R. Matheson, Robert Endre Tarjan:
Analysis of Multigrid Algorithms on Massively Parallel Computers: Architectural Implications. J. Parallel Distributed Comput. 33(1): 33-43 (1996) - 1995
- [j141]Adam L. Buchsbaum, Rajamani Sundar, Robert Endre Tarjan:
Lazy Structure Sharing for Query Optimization. Acta Informatica 32(3): 255-270 (1995) - [j140]David R. Karger, Philip N. Klein, Robert Endre Tarjan:
A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. J. ACM 42(2): 321-328 (1995) - [j139]Adam L. Buchsbaum, Robert Endre Tarjan:
Confluently Persistent Deques via Data-Structural Bootstrapping. J. Algorithms 18(3): 513-547 (1995) - [j138]Adam L. Buchsbaum, Rajamani Sundar, Robert Endre Tarjan:
Data-Structural Bootstrapping, Linear Path Compression, and Catenable Heap-Ordered Double-Ended Queues. SIAM J. Comput. 24(6): 1190-1206 (1995) - [j137]Xiaofeng Han, Pierre Kelsen, Vijaya Ramachandran, Robert Endre Tarjan:
Computing Minimal Spanning Subgraphs in Linear Time. SIAM J. Comput. 24(6): 1332-1358 (1995) - 1994
- [j136]James R. Driscoll, Daniel Dominic Sleator, Robert Endre Tarjan:
Fully Persistent Lists with Catenation. J. ACM 41(5): 943-959 (1994) - [j135]Valerie King, S. Rao, Robert Endre Tarjan:
A Faster Deterministic Maximum Flow Algorithm. J. Algorithms 17(3): 447-474 (1994) - [j134]Rajamani Sundar, Robert Endre Tarjan:
Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences. SIAM J. Comput. 23(1): 24-44 (1994) - [j133]Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, Robert Endre Tarjan:
Dynamic Perfect Hashing: Upper and Lower Bounds. SIAM J. Comput. 23(4): 738-761 (1994) - [j132]Ravindra K. Ahuja, James B. Orlin, Clifford Stein, Robert Endre Tarjan:
Improved Algorithms for Bipartite Network Flow. SIAM J. Comput. 23(5): 906-933 (1994) - 1993
- [j131]David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert Endre Tarjan, Jeffery R. Westbrook, Moti Yung:
Corrigendum: Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph. J. Algorithms 15(1): 173 (1993) - [j130]Heather Booth, Robert Endre Tarjan:
Finding the Minimum-Cost Maximum Flow in a Series-Parallel Network. J. Algorithms 15(3): 416-446 (1993) - [j129]Jiazhen Cai, Xiaofeng Han, Robert Endre Tarjan:
An O(m log n)-Time Algorithm for the Maximal Planar Subgraph Problem. SIAM J. Comput. 22(6): 1142-1162 (1993) - 1992
- [j128]Jeffery R. Westbrook, Robert Endre Tarjan:
Maintaining Bridge-Connected and Biconnected Components On-Line. Algorithmica 7(5&6): 433-464 (1992) - [j127]Bhubaneswar Mishra, Robert Endre Tarjan:
A Linear-Time Algorithm for Finding an Ambitus. Algorithmica 7(5&6): 521-554 (1992) - [j126]David G. Kirkpatrick, Maria M. Klawe, Robert Endre Tarjan:
Polygon Triangulation in O (n log log n) Time with Simple Data Structures. Discret. Comput. Geom. 7: 329-346 (1992) - [j125]Kenneth L. Clarkson, Richard Cole, Robert Endre Tarjan:
Randomized parallel algorithms for trapezoidal diagrams. Int. J. Comput. Geom. Appl. 2(2): 117-133 (1992) - [j124]Kenneth L. Clarkson, Richard Cole, Robert Endre Tarjan:
Erratum: Randomized parallel algorithms for trapezoidal diagrams. Int. J. Comput. Geom. Appl. 2(3): 341-343 (1992) - [j123]David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert Endre Tarjan, Jeffery R. Westbrook, Moti Yung:
Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph. J. Algorithms 13(1): 33-54 (1992) - [j122]Ravindra K. Ahuja, Andrew V. Goldberg, James B. Orlin, Robert Endre Tarjan:
Finding minimum-cost flows by double scaling. Math. Program. 53: 243-266 (1992) - [j121]Brandon Dixon, Monika Rauch, Robert Endre Tarjan:
Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time. SIAM J. Comput. 21(6): 1184-1192 (1992) - [j120]Daniel Dominic Sleator, Robert Endre Tarjan, William P. Thurston:
Short Encodings of Evolving Structures. SIAM J. Discret. Math. 5(3): 428-450 (1992) - [j119]Jiazhen Cai, Robert Paige, Robert Endre Tarjan:
More Efficient Bottom-Up Multi-Pattern Matching in Trees. Theor. Comput. Sci. 106(1): 21-60 (1992) - 1991
- [j118]Harold N. Gabow, Robert Endre Tarjan:
Faster Scaling Algorithms for General Graph-Matching Problems. J. ACM 38(4): 815-853 (1991) - [j117]Phillip B. Gibbons, Richard M. Karp, Vijaya Ramachandran, Danny Soroker, Robert Endre Tarjan:
Transitive Compaction in Parallel via Branchings. J. Algorithms 12(1): 110-125 (1991) - [j116]Robert E. Tarjan:
Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem. Math. Oper. Res. 16(2): 272-291 (1991) - [j115]Andrew V. Goldberg, Michael D. Grigoriadis, Robert Endre Tarjan:
Use of dynamic trees in a network simplex algorithm for the maximum flow problem. Math. Program. 50: 277-290 (1991) - [j114]Neal E. Young, Robert Endre Tarjan, James B. Orlin:
Faster parametric shortest path and minimum-balance algorithms. Networks 21(2): 205-221 (1991) - 1990
- [j113]Khun Yee Fung, Tina M. Nicholl, Robert Endre Tarjan, Christopher J. Van Wyk:
Simplified Linear-Time Jordan Sorting and Polygon Clipping. Inf. Process. Lett. 35(2): 85-92 (1990) - [j112]Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin, Robert Endre Tarjan:
Faster Algorithms for the Shortest Path Problem. J. ACM 37(2): 213-223 (1990) - [j111]Andrew V. Goldberg, Robert E. Tarjan:
Finding Minimum-Cost Circulations by Successive Approximation. Math. Oper. Res. 15(3): 430-466 (1990) - 1989
- [j110]Kenneth L. Clarkson, Robert Endre Tarjan, Christopher J. Van Wyk:
A Fast Las Vegas Algorithm for Triangulating a Simple Polygon. Discret. Comput. Geom. 4: 423-432 (1989) - [j109]David Ginat, Daniel Dominic Sleator, Robert Endre Tarjan:
A Tight Amortized Bound for Path Reversal. Inf. Process. Lett. 31(1): 3-5 (1989) - [j108]Andrew V. Goldberg, Robert Endre Tarjan:
A Parallel Algorithm for Finding a Blocking Flow in an Acyclic Network. Inf. Process. Lett. 31(5): 265-271 (1989) - [j107]Andrew V. Goldberg, Robert Endre Tarjan:
Finding minimum-cost circulations by canceling negative cycles. J. ACM 36(4): 873-886 (1989) - [j106]James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan:
Making Data Structures Persistent. J. Comput. Syst. Sci. 38(1): 86-124 (1989) - [j105]Jeffery R. Westbrook, Robert Endre Tarjan:
Amortized Analysis of Algorithms for Set Union with Backtracking. SIAM J. Comput. 18(1): 1-11 (1989) - [j104]Giorgio Gallo, Michael D. Grigoriadis, Robert Endre Tarjan:
A Fast Parametric Maximum Flow Algorithm and Applications. SIAM J. Comput. 18(1): 30-55 (1989) - [j103]Ravindra K. Ahuja, James B. Orlin, Robert Endre Tarjan:
Improved Time Bounds for the Maximum Flow Problem. SIAM J. Comput. 18(5): 939-954 (1989) - [j102]Harold N. Gabow, Robert Endre Tarjan:
Faster Scaling Algorithms for Network Problems. SIAM J. Comput. 18(5): 1013-1036 (1989) - 1988
- [j101]James R. Driscoll, Harold N. Gabow, Ruth Shrairman, Robert Endre Tarjan:
Relaxed Heaps: An Alternative to Fibonacci Heaps with Applications to Parallel Computation. Commun. ACM 31(11): 1343-1354 (1988) - [j100]Harold N. Gabow, Robert Endre Tarjan:
A Linear-Time Algorithm for Finding a Minimum Spanning Pseudoforest. Inf. Process. Lett. 27(5): 259-263 (1988) - [j99]Andrew V. Goldberg, Robert Endre Tarjan:
A new approach to the maximum-flow problem. J. ACM 35(4): 921-940 (1988) - [j98]Harold N. Gabow, Robert Endre Tarjan:
Algorithms for Two Bottleneck Optimization Problems. J. Algorithms 9(3): 411-417 (1988) - [j97]Michael R. Garey, Robert E. Tarjan, Gordon T. Wilfong:
One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties. Math. Oper. Res. 13(2): 330-348 (1988) - [j96]Robert Endre Tarjan, Christopher J. Van Wyk:
An O(n log log n)-Time Algorithm for Triangulating a Simple Polygon. SIAM J. Comput. 17(1): 143-178 (1988) - [j95]Robert Endre Tarjan, Christopher J. Van Wyk:
Erratum: An O(n log log n)-Time Algorithm for Triangulating a Simple Polygon. SIAM J. Comput. 17(5): 1061 (1988) - 1987
- [j94]Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, Robert Endre Tarjan:
Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons. Algorithmica 2: 209-233 (1987) - [j93]Robert Endre Tarjan:
Algorithmic Design. Commun. ACM 30(3): 204-212 (1987) - [j92]Michael L. Fredman, Robert Endre Tarjan:
Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3): 596-615 (1987) - [j91]Robert Paige, Robert Endre Tarjan:
Three Partition Refinement Algorithms. SIAM J. Comput. 16(6): 973-989 (1987) - 1986
- [j90]Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator, Robert Endre Tarjan:
The Pairing Heap: A New Form of Self-Adjusting Heap. Algorithmica 1(1): 111-129 (1986) - [j89]Jon Louis Bentley, Daniel Dominic Sleator, Robert Endre Tarjan, Victor K. Wei:
A Locally Adaptive Data Compression Scheme. Commun. ACM 29(4): 320-330 (1986) - [j88]Neil Sarnak, Robert Endre Tarjan:
Planar Point Location Using Persistent Search Trees. Commun. ACM 29(7): 669-679 (1986) - [j87]Harold N. Gabow, Zvi Galil, Thomas H. Spencer, Robert Endre Tarjan:
Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Comb. 6(2): 109-122 (1986) - [j86]Pierre Rosenstiehl, Robert Endre Tarjan:
Rectilinear Planar Layouts and Bipolar Orientations of Planar Graphs. Discret. Comput. Geom. 1: 343-353 (1986) - [j85]Kurt Hoffman, Kurt Mehlhorn, Pierre Rosenstiehl, Robert Endre Tarjan:
Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees. Inf. Control. 68(1-3): 170-184 (1986) - [j84]H. Gajewska, Robert Endre Tarjan:
Deques with Heap Order. Inf. Process. Lett. 22(4): 197-200 (1986) - [j83]Daniel Dominic Sleator, Robert Endre Tarjan:
Self-Adjusting Heaps. SIAM J. Comput. 15(1): 52-69 (1986) - 1985
- [j82]Daniel Dominic Sleator, Robert Endre Tarjan:
Amortized Efficiency of List Update and Paging Rules. Commun. ACM 28(2): 202-208 (1985) - [j81]Robert Endre Tarjan:
Sequential access in play trees takes linear time. Comb. 5(4): 367-378 (1985) - [j80]Robert Endre Tarjan:
Decomposition by clique separators. Discret. Math. 55(2): 221-232 (1985) - [j79]Daniel Dominic Sleator, Robert Endre Tarjan:
Self-Adjusting Binary Search Trees. J. ACM 32(3): 652-686 (1985) - [j78]Harold N. Gabow, Robert Endre Tarjan:
A Linear-Time Algorithm for a Special Case of Disjoint Set Union. J. Comput. Syst. Sci. 30(2): 209-221 (1985) - [j77]James Roskind, Robert E. Tarjan:
A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees. Math. Oper. Res. 10(4): 701-708 (1985) - [j76]Fan R. K. Chung, Michael R. Garey, Robert Endre Tarjan:
Strongly connected orientations of mixed multigraphs. Networks 15(4): 477-484 (1985) - [j75]Robert Endre Tarjan, Mihalis Yannakakis:
Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM J. Comput. 14(1): 254-255 (1985) - [j74]Samuel W. Bent, Daniel Dominic Sleator, Robert Endre Tarjan:
Biased Search Trees. SIAM J. Comput. 14(3): 545-568 (1985) - [j73]Robert Endre Tarjan, Uzi Vishkin:
An Efficient Parallel Biconnectivity Algorithm. SIAM J. Comput. 14(4): 862-874 (1985) - [j72]Robert Paige, Robert Endre Tarjan, Robert Bonic:
A Linear Time Solution to the Single Function Coarsest Partition Problem. Theor. Comput. Sci. 40: 67-84 (1985) - 1984
- [j71]Robert Endre Tarjan, Jan van Leeuwen:
Worst-case Analysis of Set Union Algorithms. J. ACM 31(2): 245-281 (1984) - [j70]Harold N. Gabow, Robert Endre Tarjan:
Efficient Algorithms for a Family of Matroid Intersection Problems. J. Algorithms 5(1): 80-131 (1984) - [j69]Pierre Rosenstiehl, Robert Endre Tarjan:
Gauss Codes, Planar Hamiltonian Graphs, and Stack-Sortable Permutations. J. Algorithms 5(3): 375-390 (1984) - [j68]John R. Gilbert, Joan P. Hutchinson, Robert Endre Tarjan:
A Separator Theorem for Graphs of Bounded Genus. J. Algorithms 5(3): 391-407 (1984) - [j67]J. W. Suurballe, Robert Endre Tarjan:
A quick method for finding shortest pairs of disjoint paths. Networks 14(2): 325-336 (1984) - [j66]Dov Harel, Robert Endre Tarjan:
Fast Algorithms for Finding Nearest Common Ancestors. SIAM J. Comput. 13(2): 338-355 (1984) - [j65]Robert Endre Tarjan, Mihalis Yannakakis:
Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM J. Comput. 13(3): 566-579 (1984) - 1983
- [j64]Joan Feigenbaum, Robert E. Tarjan:
Two new kinds of biased search trees. Bell Syst. Tech. J. 62(10): 3139-3158 (1983) - [j63]Robert Endre Tarjan:
Updating a Balanced Search Tree in O(1) Rotations. Inf. Process. Lett. 16(5): 253-257 (1983) - [j62]Robert Endre Tarjan:
An Improved Algorithm for Hierarchical Clustering Using Strong Components. Inf. Process. Lett. 17(1): 37-41 (1983) - [j61]Daniel Dominic Sleator, Robert Endre Tarjan:
A Data Structure for Dynamic Trees. J. Comput. Syst. Sci. 26(3): 362-391 (1983) - [j60]Robert Endre Tarjan:
Space-Efficient Implementations of Graph Search Methods. ACM Trans. Math. Softw. 9(3): 326-339 (1983) - 1982
- [j59]Robert Endre Tarjan:
A Hierarchical Clustering Algorithm Using Strong Components. Inf. Process. Lett. 14(1): 26-29 (1982) - [j58]Robert Endre Tarjan:
Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees. Inf. Process. Lett. 14(1): 30-33 (1982) - [j57]Thomas Lengauer, Robert Endre Tarjan:
Asymptotically tight bounds on time-space trade-offs in a pebble game. J. ACM 29(4): 1087-1130 (1982) - [j56]John H. Reif, Robert Endre Tarjan:
Symbolic Program Analysis in Almost-Linear Time. SIAM J. Comput. 11(1): 81-93 (1982) - [j55]Jacobo Valdes, Robert Endre Tarjan, Eugene L. Lawler:
The Recognition of Series Parallel Digraphs. SIAM J. Comput. 11(2): 298-313 (1982) - 1981
- [j54]Robert Endre Tarjan:
A Unified Approach to Path Problems. J. ACM 28(3): 577-593 (1981) - [j53]Robert Endre Tarjan:
Fast Algorithms for Solving Path Problems. J. ACM 28(3): 594-614 (1981) - [j52]M. R. Garey, David S. Johnson, Barbara B. Simons, Robert Endre Tarjan:
Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines. SIAM J. Comput. 10(2): 256-269 (1981) - [j51]Edward M. Reingold, Robert Endre Tarjan:
On a Greedy Heuristic for Complete Matching. SIAM J. Comput. 10(4): 676-681 (1981) - 1980
- [j50]Thomas Lengauer, Robert Endre Tarjan:
The Space Complexity of Pebble Games on Trees. Inf. Process. Lett. 10(4/5): 184-188 (1980) - [j49]Peter J. Downey, Ravi Sethi, Robert Endre Tarjan:
Variations on the Common Subexpression Problem. J. ACM 27(4): 758-771 (1980) - [j48]Richard M. Karp, Robert Endre Tarjan:
Linear Expected-Time Algorithms for Connectivity Problems. J. Algorithms 1(4): 374-393 (1980) - [j47]John R. Gilbert, Thomas Lengauer, Robert Endre Tarjan:
The Pebbling Problem is Complete in Polynomial Space. SIAM J. Comput. 9(3): 513-524 (1980) - [j46]Mark R. Brown, Robert Endre Tarjan:
Design and Analysis of a Data Structure for Representing Sorted Lists. SIAM J. Comput. 9(3): 594-614 (1980) - [j45]Richard J. Lipton, Robert Endre Tarjan:
Applications of a Planar Separator Theorem. SIAM J. Comput. 9(3): 615-627 (1980) - [j44]Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Robert Endre Tarjan:
Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms. SIAM J. Comput. 9(4): 808-826 (1980) - 1979
- [j43]Robert Endre Tarjan, Andrew Chi-Chih Yao:
Storing a Sparse Table. Commun. ACM 22(11): 606-611 (1979) - [j42]Bengt Aspvall, Michael F. Plass, Robert Endre Tarjan:
A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas. Inf. Process. Lett. 8(3): 121-123 (1979) - [j41]Mark R. Brown, Robert Endre Tarjan:
A Fast Merging Algorithm. J. ACM 26(2): 211-226 (1979) - [j40]Robert Endre Tarjan:
Applications of Path Compression on Balanced Trees. J. ACM 26(4): 690-715 (1979) - [j39]Robert Endre Tarjan:
A Class of Algorithms which Require Nonlinear Time to Maintain Disjoint Sets. J. Comput. Syst. Sci. 18(2): 110-127 (1979) - [j38]Thomas Lengauer, Robert Endre Tarjan:
A Fast Algorithm for Finding Dominators in a Flowgraph. ACM Trans. Program. Lang. Syst. 1(1): 121-141 (1979) - 1978
- [j37]Wolfgang J. Paul, Robert Endre Tarjan:
Time-Space Trade-Offs in a Pebble Game. Acta Informatica 10: 111-115 (1978) - [j36]M. R. Garey, David S. Johnson, Franco P. Preparata, Robert Endre Tarjan:
Triangulating a Simple Polygon. Inf. Process. Lett. 7(4): 175-179 (1978) - [j35]M. R. Garey, Robert Endre Tarjan:
A Linear-Time Algorithm for Finding All Feedback Vertices. Inf. Process. Lett. 7(6): 274-276 (1978) - 1977
- [j34]Wolfgang J. Paul, Robert Endre Tarjan, James R. Celoni:
Space Bounds for a Game on Graphs. Math. Syst. Theory 10: 239-251 (1977) - [j33]Wolfgang J. Paul, Robert Endre Tarjan, James R. Celoni:
Correction: Space Bounds for a Game on Graphs. Math. Syst. Theory 11: 85 (1977) - [j32]Robert Endre Tarjan:
Finding optimum branchings. Networks 7(1): 25-35 (1977) - [j31]Robert Endre Tarjan, Anthony E. Trojanowski:
Finding a Maximum Independent Set. SIAM J. Comput. 6(3): 537-546 (1977) - [j30]Shimon Even, Robert Endre Tarjan:
Corrigendum: Computing an st-Numbering. TCS 2(1976):339-344. Theor. Comput. Sci. 4(1): 123 (1977) - 1976
- [j29]Robert Endre Tarjan:
Edge-Disjoint Spanning Trees and Depth-First Search. Acta Informatica 6: 171-185 (1976) - [j28]George Markowsky, Robert Endre Tarjan:
Lower bounds on the lengths of node sequences in directed graphs. Discret. Math. 16(4): 329-337 (1976) - [j27]Shimon Even, Robert Endre Tarjan:
A Combinatorial Problem Which Is Complete in Polynomial Space. J. ACM 23(4): 710-719 (1976) - [j26]Gideon Ehrlich, Shimon Even, Robert Endre Tarjan:
Intersection graphs of curves in the plane. J. Comb. Theory, Ser. B 21(1): 8-20 (1976) - [j25]Seymour E. Goodman, Stephen T. Hedetniemi, Robert Endre Tarjan:
b-Matchings in Trees. SIAM J. Comput. 5(1): 104-108 (1976) - [j24]Donald J. Rose, Robert Endre Tarjan, George S. Lueker:
Algorithmic Aspects of Vertex Elimination on Graphs. SIAM J. Comput. 5(2): 266-283 (1976) - [j23]Kapali P. Eswaran, Robert Endre Tarjan:
Augmentation Problems. SIAM J. Comput. 5(4): 653-665 (1976) - [j22]M. R. Garey, David S. Johnson, Robert Endre Tarjan:
The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM J. Comput. 5(4): 704-714 (1976) - [j21]David R. Cheriton, Robert Endre Tarjan:
Finding Minimum Spanning Trees. SIAM J. Comput. 5(4): 724-742 (1976) - [j20]Shimon Even, Robert Endre Tarjan:
Computing an st -Numbering. Theor. Comput. Sci. 2(3): 339-344 (1976) - 1975
- [j19]Jayadev Misra, Robert Endre Tarjan:
Optimal Chain Partitions of Trees. Inf. Process. Lett. 4(1): 24-26 (1975) - [j18]Robert Endre Tarjan:
Efficiency of a Good But Not Linear Set Union Algorithm. J. ACM 22(2): 215-225 (1975) - [j17]Ronald C. Read, Robert E. Tarjan:
Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees. Networks 5(3): 237-252 (1975) - [j16]Shimon Even, Robert Endre Tarjan:
Network Flow and Testing Graph Connectivity. SIAM J. Comput. 4(4): 507-518 (1975) - 1974
- [j15]Robert Endre Tarjan:
A Note on Finding the Bridges of a Graph. Inf. Process. Lett. 2(6): 160-161 (1974) - [j14]Robert Endre Tarjan:
A New Algorithm for Finding Weak Components. Inf. Process. Lett. 3(1): 13-15 (1974) - [j13]Robert Endre Tarjan:
A Good Algorithm for Edge-Disjoint Branching. Inf. Process. Lett. 3(2): 51-53 (1974) - [j12]John E. Hopcroft, Robert Endre Tarjan:
Efficient Planarity Testing. J. ACM 21(4): 549-568 (1974) - [j11]Robert Endre Tarjan:
Testing Flow Graph Reducibility. J. Comput. Syst. Sci. 9(3): 355-365 (1974) - [j10]Robert Endre Tarjan:
Finding Dominators in Directed Graphs. SIAM J. Comput. 3(1): 62-89 (1974) - 1973
- [j9]John E. Hopcroft, Robert Endre Tarjan:
Efficient Algorithms for Graph Manipulation [H] (Algorithm 447). Commun. ACM 16(6): 372-378 (1973) - [j8]John E. Hopcroft, Robert Endre Tarjan:
A V log V Algorithm for Isomorphism of Triconnected Planar Graphs. J. Comput. Syst. Sci. 7(3): 323-331 (1973) - [j7]Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, Robert Endre Tarjan:
Time Bounds for Selection. J. Comput. Syst. Sci. 7(4): 448-461 (1973) - [j6]John E. Hopcroft, Robert Endre Tarjan:
Dividing a Graph into Triconnected Components. SIAM J. Comput. 2(3): 135-158 (1973) - [j5]Robert Endre Tarjan:
Enumeration of the Elementary Circuits of a Directed Graph. SIAM J. Comput. 2(3): 211-216 (1973) - 1972
- [j4]Robert Endre Tarjan:
Determining Whether a Groupoid is a Group. Inf. Process. Lett. 1(3): 120-124 (1972) - [j3]Robert Endre Tarjan:
Sorting Using Networks of Queues and Stacks. J. ACM 19(2): 341-346 (1972) - [j2]Robert Endre Tarjan:
Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160 (1972) - 1971
- [j1]John E. Hopcroft, Robert Endre Tarjan:
A V² Algorithm for Determining Isomorphism of Planar Graphs. Inf. Process. Lett. 1(1): 32-34 (1971)
Conference and Workshop Papers
- 2024
- [c127]Dani Dorfman, Haim Kaplan, Robert E. Tarjan, Mikkel Thorup, Uri Zwick:
Minimum-cost paths for electric cars. SOSA 2024: 374-382 - 2023
- [c126]Dani Dorfman, Haim Kaplan, Robert E. Tarjan, Uri Zwick:
Optimal Energetic Paths for Electric Cars. ESA 2023: 42:1-42:17 - [c125]Corwin Sinnamon, Robert E. Tarjan:
A Nearly-Tight Analysis of Multipass Pairing Heaps. SODA 2023: 535-548 - [c124]Corwin Sinnamon, Robert E. Tarjan:
A Tight Analysis of Slim Heaps and Smooth Heaps. SODA 2023: 549-567 - [c123]Robert E. Tarjan, Uri Zwick:
Optimal resizable arrays. SOSA 2023: 285-304 - [c122]Ofek Gila, Michael T. Goodrich, Robert E. Tarjan:
Zip-Zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent. WADS 2023: 474-492 - 2022
- [c121]Haim Kaplan, Robert E. Tarjan, Or Zamir, Uri Zwick:
Simulating a stack using queues. SODA 2022: 1901-1924 - 2021
- [c120]Maria Hartmann, László Kozma, Corwin Sinnamon, Robert E. Tarjan:
Analysis of Smooth Heaps and Slim Heaps. ICALP 2021: 79:1-79:20 - [c119]Sepehr Assadi, S. Cliff Liu, Robert E. Tarjan:
An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models. SOSA 2021: 165-171 - 2020
- [c118]Sixue Cliff Liu, Robert E. Tarjan, Peilin Zhong:
Connected Components on a PRAM in Log Diameter Time. SPAA 2020: 359-369 - 2019
- [c117]Siddhartha V. Jayanti, Robert E. Tarjan, Enric Boix-Adserà:
Randomized Concurrent Set Union and Generalized Wake-Up. PODC 2019: 187-196 - [c116]Sixue Liu, Robert E. Tarjan:
Simple Concurrent Labeling Algorithms for Connected Components. SOSA 2019: 3:1-3:20 - [c115]Caleb C. Levy, Robert E. Tarjan:
A New Path from Splay to Dynamic Optimality. SODA 2019: 1311-1330 - [c114]Caleb C. Levy, Robert E. Tarjan:
Splaying Preorders and Postorders. WADS 2019: 510-522 - [c113]Robert E. Tarjan, Caleb C. Levy, Stephen Timmel:
Zip Trees. WADS 2019: 566-577 - 2016
- [c112]Siddhartha V. Jayanti, Robert E. Tarjan:
A Randomized Concurrent Algorithm for Disjoint Set Union. PODC 2016: 75-82 - 2015
- [c111]Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Pushmeet Kohli, Robert Endre Tarjan, Renato F. Werneck:
Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search. ESA 2015: 619-630 - [c110]Thomas Dueholm Hansen, Haim Kaplan, Robert Endre Tarjan, Uri Zwick:
Hollow Heaps. ICALP (1) 2015: 689-700 - [c109]Andrew V. Goldberg, Haim Kaplan, Sagi Hed, Robert Endre Tarjan:
Minimum Cost Flows in Graphs with Unit Capacities. STACS 2015: 406-419 - 2014
- [c108]Daniel H. Larkin, Siddhartha Sen, Robert Endre Tarjan:
A Back-to-Basics Empirical Study of Priority Queues. ALENEX 2014: 61-72 - [c107]Daniel H. Larkin, Robert Endre Tarjan:
Nested Set Union. ESA 2014: 618-629 - [c106]Ashish Goel, Sanjeev Khanna, Daniel H. Larkin, Robert Endre Tarjan:
Disjoint Set Union with Randomized Linking. SODA 2014: 1005-1017 - [c105]Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, Virginia Vassilevska Williams:
Better Approximation Algorithms for the Graph Diameter. SODA 2014: 1041-1052 - [c104]Loukas Georgiadis, Luigi Laura, Nikos Parotsidis, Robert Endre Tarjan:
Loop Nesting Forests, Dominators, and Applications. SEA 2014: 174-186 - 2013
- [c103]Loukas Georgiadis, Luigi Laura, Nikos Parotsidis, Robert Endre Tarjan:
Dominator Certification and Independent Spanning Trees: An Experimental Study. SEA 2013: 284-295 - 2012
- [c102]Christos H. Papadimitriou, Leonard M. Adleman, Richard M. Karp, Donald E. Knuth, Robert E. Tarjan, Leslie G. Valiant:
An Algorithmic View of the Universe. ACM-TURING 2012: 13:1 - [c101]Lyle Ramshaw, Robert Endre Tarjan:
A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in Bipartite Graphs. FOCS 2012: 581-590 - [c100]Loukas Georgiadis, Robert Endre Tarjan:
Dominators, Directed Bipolar Orders, and Independent Spanning Trees. ICALP (1) 2012: 375-386 - [c99]Gerth Stølting Brodal, George Lagogiannis, Robert Endre Tarjan:
Strict fibonacci heaps. STOC 2012: 1177-1184 - [c98]Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, Robert Endre Tarjan:
CBTree: A Practical Concurrent Self-Adjusting Search Tree. DISC 2012: 1-15 - 2011
- [c97]Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Robert Endre Tarjan, Renato Fonseca F. Werneck:
Maximum Flows by Incremental Breadth-First Search. ESA 2011: 457-468 - [c96]Robert Endre Tarjan:
Theory vs. Practice in the Design and Analysis of Algorithms. WADS 2011: 703 - 2010
- [c95]Siddhartha Sen, Robert Endre Tarjan:
Deletion Without Rebalancing in Balanced Binary Trees. SODA 2010: 1490-1499 - 2009
- [c94]Andrew Byde, Terence Kelly, Yunhong Zhou, Robert Endre Tarjan:
Efficiently Generating k-Best Solutions to Procurement Auctions. AAIM 2009: 68-84 - [c93]Loukas Georgiadis, Andrew V. Goldberg, Robert Endre Tarjan, Renato Fonseca F. Werneck:
An Experimental Study of Minimum Mean Cycle Algorithms. ALENEX 2009: 1-13 - [c92]Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan:
Rank-Pairing Heaps. ESA 2009: 659-670 - [c91]Siddhartha Sen, Robert Endre Tarjan:
Deletion without Rebalancing in Multiway Search Trees. ISAAC 2009: 832-841 - [c90]Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan:
Rank-Balanced Trees. WADS 2009: 351-362 - 2008
- [c89]Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert Endre Tarjan, Renato Fonseca F. Werneck:
Shortest Path Feasibility Algorithms: An Experimental Evaluation. ALENEX 2008: 118-132 - [c88]Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan:
Faster Algorithms for Incremental Topological Ordering. ICALP (1) 2008: 421-433 - [c87]Robert Endre Tarjan:
Reachability Problems on Directed Graphs. ISAAC 2008: 3 - [c86]Alina Ene, William G. Horne, Nikola Milosavljevic, Prasad Rao, Robert Schreiber, Robert Endre Tarjan:
Fast exact and heuristic methods for role minimization problems. SACMAT 2008: 1-10 - 2007
- [c85]Nina Mishra, Robert Schreiber, Isabelle Stanton, Robert Endre Tarjan:
Clustering Social Networks. WAW 2007: 56-67 - [c84]Robert Endre Tarjan, Renato Fonseca F. Werneck:
Dynamic Trees in Practice. WEA 2007: 80-93 - [c83]Maxim A. Babenko, Jonathan Derryberry, Andrew V. Goldberg, Robert Endre Tarjan, Yunhong Zhou:
Experimental Evaluation of Parametric Max-Flow Algorithms. WEA 2007: 256-269 - 2006
- [c82]Robert Endre Tarjan, Julie Ward, Bin Zhang, Yunhong Zhou, Jia Mao:
Balancing Applied to Maximum Network Flow Problems. ESA 2006: 612-623 - [c81]Loukas Georgiadis, Robert Endre Tarjan, Renato Fonseca F. Werneck:
Design of data structures for mergeable trees. SODA 2006: 394-403 - [c80]Robert Endre Tarjan:
Results and Problems on Self-adjusting Search Trees and Related Data Structures. SWAT 2006: 2 - 2005
- [c79]Kamalika Chaudhuri, Anshul Kothari, Rudi Pendavingh, Ram Swaminathan, Robert Endre Tarjan, Yunhong Zhou:
Server Allocation Algorithms for Tiered Systems. COCOON 2005: 632-643 - [c78]Eric Anderson, Dirk Beyer, Kamalika Chaudhuri, Terence Kelly, Norman Salazar, Cipriano A. Santos, Ram Swaminathan, Robert Endre Tarjan, Janet L. Wiener, Yunhong Zhou:
Deadline scheduling for animation rendering. SIGMETRICS 2005: 384-385 - [c77]Loukas Georgiadis, Robert Endre Tarjan:
Dominator tree verification and vertex-disjoint paths. SODA 2005: 433-442 - [c76]Robert Endre Tarjan, Renato Fonseca F. Werneck:
Self-adjusting top trees. SODA 2005: 813-822 - [c75]Eric Anderson, Dirk Beyer, Kamalika Chaudhuri, Terence Kelly, Norman Salazar, Cipriano A. Santos, Ram Swaminathan, Robert Endre Tarjan, Janet L. Wiener, Yunhong Zhou:
Value-maximizing deadline scheduling and its application to animation rendering. SPAA 2005: 299-308 - 2004
- [c74]Loukas Georgiadis, Renato Fonseca F. Werneck, Robert Endre Tarjan, Spyridon Triantafyllis, David I. August:
Finding Dominators in Practice. ESA 2004: 677-688 - [c73]Loukas Georgiadis, Robert Endre Tarjan:
Finding dominators revisited: extended abstract. SODA 2004: 869-878 - [c72]Ran Mendelson, Robert Endre Tarjan, Mikkel Thorup, Uri Zwick:
Melding Priority Queues. SWAT 2004: 223-235 - 2003
- [c71]Haim Kaplan, Eyal Molad, Robert Endre Tarjan:
Dynamic rectangular intersection with priorities. STOC 2003: 639-648 - 2002
- [c70]Haim Kaplan, Nira Shafrir, Robert Endre Tarjan:
Union-find with deletions. SODA 2002: 19-28 - [c69]Haim Kaplan, Nira Shafrir, Robert Endre Tarjan:
Meldable heaps and boolean union-find. STOC 2002: 573-582 - 2001
- [c68]Bill G. Horne, Lesley R. Matheson, Casey Sheehan, Robert Endre Tarjan:
Dynamic Self-Checking Techniques for Improved Tamper Resistance. Digital Rights Management Workshop 2001: 141-159 - [c67]Haim Kaplan, Robert Endre Tarjan, Kostas Tsioutsiouliklis:
Faster kinetic heaps and their use in broadcast scheduling. SODA 2001: 836-844 - 1999
- [c66]Harold N. Gabow, Haim Kaplan, Robert Endre Tarjan:
Unique Maximum Matching Algorithms. STOC 1999: 70-78 - 1998
- [c65]Lesley R. Matheson, Stephen G. Mitchell, Talal Shamoon, Robert Endre Tarjan, Francis Zane:
Robustness and Security of Digital Watermarks. Financial Cryptography 1998: 227-240 - [c64]Lesley R. Matheson, Talal Shamoon, Robert Endre Tarjan:
Culturally-Induced Information Impactedness: A Prescription for Failure in Software Ventures. HICSS (6) 1998: 329-338 - [c63]Haim Kaplan, Chris Okasaki, Robert Endre Tarjan:
Simple Confluently Persistent Catenable Lists (Extended Abstract). SWAT 1998: 119-130 - 1997
- [c62]Haim Kaplan, Ron Shamir, Robert Endre Tarjan:
Faster and simpler algorithm for sorting signed permutations by reversals. RECOMB 1997: 163 - [c61]Haim Kaplan, Ron Shamir, Robert Endre Tarjan:
Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals. SODA 1997: 344-351 - 1996
- [c60]Susan E. Dorward, Lesley R. Matheson, Robert Endre Tarjan:
Toward Efficient Unstructured Multigrid Preprocessing (Extended Abstract). IRREGULAR 1996: 105-118 - [c59]Richard Cole, Philip N. Klein, Robert Endre Tarjan:
Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling. SPAA 1996: 243-250 - [c58]Haim Kaplan, Robert Endre Tarjan:
Purely Functional Representations of Catenable Sorted Lists. STOC 1996: 202-211 - 1995
- [c57]Bruce M. Maggs, Lesley R. Matheson, Robert Endre Tarjan:
Models of parallel computation: a survey and synthesis. HICSS (2) 1995: 61-72 - [c56]Haim Kaplan, Robert Endre Tarjan:
Persistent lists with catenation via recursive slow-down. STOC 1995: 93-102 - [c55]Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman:
Tight analyses of two local load balancing algorithms. STOC 1995: 548-558 - 1994
- [c54]Brandon Dixon, Robert Endre Tarjan:
Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time. Canada-France Conference on Parallel and Distributed Computing 1994: 13-22 - [c53]Haim Kaplan, Ron Shamir, Robert Endre Tarjan:
Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping. FOCS 1994: 780-791 - [c52]Susan E. Dorward, Lesley R. Matheson, Robert Endre Tarjan:
Unstructured Multigrid Strategies on Massively Parallel Computers: A Case for Integrated Design. HICSS (2) 1994: 169-178 - [c51]Philip N. Klein, Robert Endre Tarjan:
A randomized linear-time algorithm for finding minimum spanning trees. STOC 1994: 9-15 - 1993
- [c50]Adam L. Buchsbaum, Robert Endre Tarjan:
Confluently Persistent Deques via Data Structural Bootstrapping. SODA 1993: 155-164 - 1992
- [c49]Adam L. Buchsbaum, Rajamani Sundar, Robert Endre Tarjan:
Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues. FOCS 1992: 40-49 - [c48]Xiaofeng Han, Pierre Kelsen, Vijaya Ramachandran, Robert Endre Tarjan:
Computing Minimal Spanning Subgraphs in Linear Time. SODA 1992: 146-156 - [c47]Valerie King, S. Rao, Robert Endre Tarjan:
A Faster Deterministic Maximum Flow Algorithm. SODA 1992: 157-164 - 1991
- [c46]Kenneth L. Clarkson, Richard Cole, Robert Endre Tarjan:
Randomized Parallel Algorithms for Trapezoidal Diagrams. SCG 1991: 152-161 - [c45]James R. Driscoll, Daniel Dominic Sleator, Robert Endre Tarjan:
Fully Persistent Lists with Catenation. SODA 1991: 89-99 - 1990
- [c44]Jiazhen Cai, Robert Paige, Robert Endre Tarjan:
More Efficient Bottom-Up Tree Pattern Matching. CAAP 1990: 72-86 - [c43]David G. Kirkpatrick, Maria M. Klawe, Robert Endre Tarjan:
Polygon Triangulation in O(n log log n) Time with Simple Data-Structures. SCG 1990: 34-43 - [c42]David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert Endre Tarjan, Jeffery R. Westbrook, Moti Yung:
Maintenance of a Minimum Spanning Forest in a Dynamic Planar Graph. SODA 1990: 1-11 - [c41]Rajamani Sundar, Robert Endre Tarjan:
Unique Binary Search Tree Representations and Equality-testing of Sets and Sequences. STOC 1990: 18-25 - 1988
- [c40]Kenneth L. Clarkson, Robert Endre Tarjan, Christopher J. Van Wyk:
A Fast Las Vegas Algorithm for Triangulating a Simple Polygon. SCG 1988: 18-22 - [c39]Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, Robert Endre Tarjan:
Dynamic Perfect Hashing: Upper and Lower Bounds. FOCS 1988: 524-531 - [c38]Andrew V. Goldberg, Robert Endre Tarjan:
Finding Minimum-Cost Circulations by Canceling Negative Cycles. STOC 1988: 388-397 - [c37]Harold N. Gabow, Robert Endre Tarjan:
Almost-Optimum Speed-ups of Algorithms for Bipartite Matching and Related Problems. STOC 1988: 514-527 - 1987
- [c36]Robert Endre Tarjan, Christopher J. Van Wyk:
Correction to "A Linear-Time Algorithm for Triangulating Simple Polygons". FOCS 1987: 486 - [c35]Andrew V. Goldberg, Robert Endre Tarjan:
Solving Minimum-Cost Flow Problems by Successive Approximation. STOC 1987: 7-18 - 1986
- [c34]Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, Robert Endre Tarjan:
Linear Time Algorithms for Visibility and Shortest Path Problems Inside Simple Polygons. SCG 1986: 1-13 - [c33]James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan:
Making Data Structures Persistent. STOC 1986: 109-121 - [c32]Daniel Dominic Sleator, Robert Endre Tarjan, William P. Thurston:
Rotation Distance, Triangulations, and Hyperbolic Geometry. STOC 1986: 122-135 - [c31]Andrew V. Goldberg, Robert Endre Tarjan:
A New Approach to the Maximum Flow Problem. STOC 1986: 136-146 - [c30]Robert Endre Tarjan, Christopher J. Van Wyk:
A Linear-Time Algorithm for Triangulating Simple Polygons. STOC 1986: 380-388 - 1985
- [c29]Kurt Hoffman, Kurt Mehlhorn, Pierre Rosenstiehl, Robert Endre Tarjan:
Sorting Jordan sequences in linear time. SCG 1985: 196-203 - 1984
- [c28]Robert Endre Tarjan, Uzi Vishkin:
Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary). FOCS 1984: 12-20 - [c27]Michael L. Fredman, Robert Endre Tarjan:
Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. FOCS 1984: 338-346 - [c26]Robert Paige, Robert Endre Tarjan:
A Linear Time Algorithm to Solve the Single Function Coarsest Partition Problem. ICALP 1984: 371-379 - [c25]Harold N. Gabow, Jon Louis Bentley, Robert Endre Tarjan:
Scaling and Related Techniques for Geometry Problems. STOC 1984: 135-143 - [c24]Daniel Dominic Sleator, Robert Endre Tarjan:
Amortized Efficiency of List Update Rules. STOC 1984: 488-492 - 1983
- [c23]Daniel Dominic Sleator, Robert Endre Tarjan:
Self-Adjusting Binary Trees. STOC 1983: 235-245 - [c22]Harold N. Gabow, Robert Endre Tarjan:
A Linear-Time Algorithm for a Special Case of Disjoint Set Union. STOC 1983: 246-251 - 1981
- [c21]Daniel Dominic Sleator, Robert Endre Tarjan:
A Data Structure for Dynamic Trees. STOC 1981: 114-122 - 1980
- [c20]Samuel W. Bent, Daniel Dominic Sleator, Robert Endre Tarjan:
Biased 2-3 Trees. FOCS 1980: 248-254 - [c19]Robert Endre Tarjan:
Prime Subprogram Parsing of a Program. POPL 1980: 95-105 - [c18]Richard M. Karp, Robert Endre Tarjan:
Linear Expected-Time Algorithms for Connectivity Problems (Extended Abstract). STOC 1980: 368-377 - 1979
- [c17]Harold N. Gabow, Robert Endre Tarjan:
Efficient Algorithms for Simple Matroid Intersection Problems. FOCS 1979: 196-204 - [c16]Jacobo Valdes, Robert Endre Tarjan, Eugene L. Lawler:
The recognition of Series Parallel digraphs. STOC 1979: 1-12 - [c15]John R. Gilbert, Thomas Lengauer, Robert Endre Tarjan:
The Pebbling Problem is Complete in Polynomial Space. STOC 1979: 237-248 - [c14]Thomas Lengauer, Robert Endre Tarjan:
Upper and Lower Bounds on Time-Space Tradeoffs. STOC 1979: 262-277 - 1978
- [c13]Mark R. Brown, Robert Endre Tarjan:
A Representation for Linear Lists with Movable Fingers. STOC 1978: 19-29 - 1977
- [c12]Richard J. Lipton, Robert Endre Tarjan:
Application of a Planar Separator Theorem. FOCS 1977: 162-170 - [c11]Wolfgang J. Paul, Robert Endre Tarjan:
Time-Space Trade-Offs in a Pebble Game. ICALP 1977: 365-369 - [c10]Robert Endre Tarjan:
Reference Machines Require Non-linear Time to Maintain Disjoint Sets. STOC 1977: 18-29 - 1976
- [c9]Wolfgang J. Paul, Robert Endre Tarjan, James R. Celoni:
Space Bounds for a Game of Graphs. STOC 1976: 149-160 - 1975
- [c8]Shimon Even, Robert Endre Tarjan:
a Combinatorial Problem which is Complete in Polynomial Space. STOC 1975: 66-71 - [c7]Donald J. Rose, Robert Endre Tarjan:
Algorithmic Aspects of Vertex Elimination. STOC 1975: 245-254 - 1974
- [c6]Robert Endre Tarjan:
Testing Graph Connectivity. STOC 1974: 185-193 - 1973
- [c5]Robert Endre Tarjan:
Testing Flow Graph Reducibility. STOC 1973: 96-107 - 1972
- [c4]John E. Hopcroft, Robert Endre Tarjan:
Isomorphism of Planar Graphs. Complexity of Computer Computations 1972: 131-152 - [c3]Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, Robert Endre Tarjan:
Linear Time Bounds for Median Computations. STOC 1972: 119-124 - 1971
- [c2]Robert Endre Tarjan:
Depth-First Search and Linear Graph Algorithms (Working Paper). SWAT 1971: 114-121 - [c1]John E. Hopcroft, Robert Endre Tarjan:
Planarity Testing in V log V Steps: Extended Abstract. IFIP Congress (1) 1971: 85-90
Parts in Books or Collections
- 2003
- [p1]Stuart Haber, Bill G. Horne, Joe Pato, Tomas Sander, Robert Endre Tarjan:
If Piracy Is the Problem, Is DRM the Answer? Digital Rights Management 2003: 224-233
Editorship
- 1999
- [e1]Robert Endre Tarjan, Tandy J. Warnow:
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17-19 January 1999, Baltimore, Maryland, USA. ACM/SIAM 1999, ISBN 0-89871-434-6 [contents]
Informal and Other Publications
- 2024
- [i30]Dani Dorfman, Haim Kaplan, Robert E. Tarjan, Mikkel Thorup, Uri Zwick:
Minimum-cost paths for electric cars. CoRR abs/2403.16936 (2024) - 2023
- [i29]Dani Dorfman, Haim Kaplan, Robert E. Tarjan, Uri Zwick:
Optimal energetic paths for electric cars. CoRR abs/2305.19015 (2023) - [i28]Corwin Sinnamon, Robert E. Tarjan:
Efficiency of Self-Adjusting Heaps. CoRR abs/2307.02772 (2023) - [i27]Ofek Gila, Michael T. Goodrich, Robert E. Tarjan:
Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent. CoRR abs/2307.07660 (2023) - [i26]Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek:
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps. CoRR abs/2311.11793 (2023) - 2022
- [i25]Robert E. Tarjan, Uri Zwick:
Finding Strong Components Using Depth-First Search. CoRR abs/2201.07197 (2022) - [i24]Corwin Sinnamon, Robert E. Tarjan:
A Simpler Proof that Pairing Heaps Take O(1) Amortized Time per Insertion. CoRR abs/2208.11791 (2022) - [i23]Robert E. Tarjan, Uri Zwick:
Optimal resizable arrays. CoRR abs/2211.11009 (2022) - 2021
- [i22]Maria Hartmann, László Kozma, Corwin Sinnamon, Robert E. Tarjan:
Analysis of Smooth Heaps and Slim Heaps. CoRR abs/2107.04919 (2021) - 2020
- [i21]S. Cliff Liu, Robert E. Tarjan, Peilin Zhong:
Connected Components on a PRAM in Log Diameter Time. CoRR abs/2003.00614 (2020) - [i20]Siddhartha V. Jayanti, Robert E. Tarjan:
Concurrent Disjoint Set Union. CoRR abs/2003.01203 (2020) - 2019
- [i19]Caleb C. Levy, Robert E. Tarjan:
Splaying Preorders and Postorders. CoRR abs/1907.06309 (2019) - [i18]Caleb C. Levy, Robert E. Tarjan:
New Paths from Splay to Dynamic Optimality. CoRR abs/1907.06310 (2019) - 2018
- [i17]Robert E. Tarjan, Caleb C. Levy:
Zip Trees. CoRR abs/1806.06726 (2018) - [i16]Sixue Liu, Robert E. Tarjan:
Simple Concurrent Labeling Algorithms for Connected Components. CoRR abs/1812.06177 (2018) - 2016
- [i15]Siddhartha V. Jayanti, Robert E. Tarjan:
A Randomized Concurrent Algorithm for Disjoint Set Union. CoRR abs/1612.01514 (2016) - 2015
- [i14]Mahdi Amani, Kevin A. Lai, Robert Endre Tarjan:
Amortized Rotation Cost in AVL Trees. CoRR abs/1506.03528 (2015) - [i13]Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan, Uri Zwick:
Hollow Heaps. CoRR abs/1510.06535 (2015) - [i12]Loukas Georgiadis, Robert E. Tarjan:
A Note on Fault Tolerant Reachability for Directed Graphs. CoRR abs/1511.07741 (2015) - 2014
- [i11]Daniel H. Larkin, Siddhartha Sen, Robert Endre Tarjan:
A Back-to-Basics Empirical Study of Priority Queues. CoRR abs/1403.0252 (2014) - [i10]Haim Kaplan, Robert Endre Tarjan, Uri Zwick:
Fibonacci Heaps Revisited. CoRR abs/1407.5750 (2014) - 2013
- [i9]Wojciech Fraczak, Loukas Georgiadis, Andrew Miller, Robert Endre Tarjan:
Finding Dominators via Disjoint Set Union. CoRR abs/1310.2118 (2013) - 2012
- [i8]Loukas Georgiadis, Robert Endre Tarjan:
Dominator Tree Certification and Independent Spanning Trees. CoRR abs/1210.8303 (2012) - 2011
- [i7]Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan:
Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance. CoRR abs/1105.2397 (2011) - [i6]Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Robert Endre Tarjan:
A New Approach to Incremental Cycle Detection and Related Problems. CoRR abs/1112.0784 (2011) - 2009
- [i5]Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan:
Heaps Simplified. CoRR abs/0903.0116 (2009) - 2008
- [i4]Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan:
Incremental Topological Ordering and Strong Component Maintenance. CoRR abs/0803.0792 (2008) - 2007
- [i3]Loukas Georgiadis, Haim Kaplan, Nira Shafrir, Robert Endre Tarjan, Renato Fonseca F. Werneck:
Data Structures for Mergeable Trees. CoRR abs/0711.1682 (2007) - [i2]Bernhard Haeupler, Robert Endre Tarjan:
Finding a Feasible Flow in a Strongly Connected Network. CoRR abs/0711.2710 (2007) - 2002
- [i1]Neal E. Young, Robert Endre Tarjan, James B. Orlin:
Faster Parametric Shortest Path and Minimum Balance Algorithms. CoRR cs.DS/0205041 (2002)
Coauthor Index
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-11 22:54 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
