default search action
Robert 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
2020 – today
- 2024
- [j188]Robert E. Tarjan, Uri Zwick:
Finding strong components using depth-first search. Eur. J. Comb. 119: 103815 (2024) - [j187]Robert E. Tarjan, Uri Zwick:
Optimal Resizable Arrays. SIAM J. Comput. 53(5): 1354-1380 (2024) - [c128]Siddhartha Jayanti, Robert E. Tarjan:
Fast, Scalable, and Machine-Verified Multicore Disjoint Set Union Data Structures and their Wide Deployment in Parallel Algorithms (Abstract). HOPC@SPAA 2024 - [c127]Dani Dorfman, Haim Kaplan, Robert E. Tarjan, Mikkel Thorup, Uri Zwick:
Minimum-cost paths for electric cars. SOSA 2024: 374-382 - [i32]Dani Dorfman, Haim Kaplan, Robert E. Tarjan, Mikkel Thorup, Uri Zwick:
Minimum-cost paths for electric cars. CoRR abs/2403.16936 (2024) - [i31]Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhon, Robert E. Tarjan, Jakub Tetek:
Fast and Simple Sorting Using Partial Information. CoRR abs/2404.04552 (2024) - [i30]Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek:
Bidirectional Dijkstra's Algorithm is Instance-Optimal. CoRR abs/2410.14638 (2024) - 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 - [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
- [j186]Sixue Cliff Liu, Robert Endre Tarjan:
Simple Concurrent Connected Components Algorithms. ACM Trans. Parallel Comput. 9(2): 9:1-9:26 (2022) - [c121]Haim Kaplan, Robert E. Tarjan, Or Zamir, Uri Zwick:
Simulating a stack using queues. SODA 2022: 1901-1924 - [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
- [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) - [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 - [i22]Maria Hartmann, László Kozma, Corwin Sinnamon, Robert E. Tarjan:
Analysis of Smooth Heaps and Slim Heaps. CoRR abs/2107.04919 (2021) - 2020
- [c118]Sixue Cliff Liu, Robert E. Tarjan, Peilin Zhong:
Connected Components on a PRAM in Log Diameter Time. SPAA 2020: 359-369 - [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)
2010 – 2019
- 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 - [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) - 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) - [c112]Siddhartha V. Jayanti, Robert E. Tarjan:
A Randomized Concurrent Algorithm for Disjoint Set Union. PODC 2016: 75-82 - [i15]Siddhartha V. Jayanti, Robert E. Tarjan:
A Randomized Concurrent Algorithm for Disjoint Set Union. CoRR abs/1612.01514 (2016) - 2015
- [j176]Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan:
Rank-Balanced Trees. ACM Trans. Algorithms 11(4): 30:1-30:26 (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 - [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
- [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) - [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 - [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
- [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) - [c103]Loukas Georgiadis, Luigi Laura, Nikos Parotsidis, Robert Endre Tarjan:
Dominator Certification and Independent Spanning Trees: An Experimental Study. SEA 2013: 284-295 - [i9]Wojciech Fraczak, Loukas Georgiadis, Andrew Miller, Robert Endre Tarjan:
Finding Dominators via Disjoint Set Union. CoRR abs/1310.2118 (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) - [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 - [i8]Loukas Georgiadis, Robert Endre Tarjan:
Dominator Tree Certification and Independent Spanning Trees. CoRR abs/1210.8303 (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) - [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 - [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) - 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 - [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) - [c95]Siddhartha Sen, Robert Endre Tarjan:
Deletion Without Rebalancing in Balanced Binary Trees. SODA 2010: 1490-1499
2000 – 2009
- 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) - [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 - [i5]Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan:
Heaps Simplified. CoRR abs/0903.0116 (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) - [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 - [i4]Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan:
Incremental Topological Ordering and Strong Component Maintenance. CoRR abs/0803.0792 (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) - [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 - [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) - 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) - [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]