Amortized Computational Complexity
From MaRDI portal
Publication:3735083
DOI10.1137/0606031zbMath0599.68046OpenAlexW1987927249WikidataQ56172073 ScholiaQ56172073MaRDI QIDQ3735083
Publication date: 1985
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0606031
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Research exposition (monographs, survey articles) pertaining to computer science (68-02)
Related Items (93)
Efficient dual simplex algorithms for the assignment problem ⋮ The list update problem and the retrieval of sets ⋮ Average cost of Duval's algorithm for generating Lyndon words ⋮ Efficient algorithms for finding minimum spanning trees in undirected and directed graphs ⋮ ATLAS: automated amortised complexity analysis of self-adjusting data structures ⋮ The pairing heap: A new form of self-adjusting heap ⋮ Semi-dynamic shortest paths and breadth-first search in digraphs ⋮ Simple confluently persistent catenable lists ⋮ Lower bounds for monotonic list labeling ⋮ Fast meldable priority queues ⋮ Selectively-amortized resource bounding ⋮ Amortized efficiency of a path retrieval data structure ⋮ Fractional cascading. I: A data structuring technique ⋮ Mechanical translation of set theoretic problem specifications into efficient RAM code - a case study ⋮ Rank-Balanced Trees ⋮ On top-down splaying ⋮ A data structure for arc insertion and regular path finding ⋮ Batch RSA ⋮ Complexity and resource bound analysis of imperative programs using difference constraints ⋮ Type-based cost analysis for lazy functional languages ⋮ Finding paths and deleting edges in directed acyclic graphs ⋮ Making data structures persistent ⋮ Splay trees as priority queues ⋮ A partially persistent data structure for the set-union problem ⋮ Connected component and simple polygon intersection searching ⋮ Topologically sweeping an arrangement ⋮ Can Burrows-Wheeler transform be replaced in chain code compression? ⋮ Worst-case analysis of the set-union problem with extended backtracking ⋮ An on-line graph coloring algorithm with sublinear performance ratio ⋮ Deletion without rebalancing in multiway search trees ⋮ Semi-online scheduling: a survey ⋮ Amortized Complexity Verified ⋮ Relaxed balance through standard rotations ⋮ A study on splay trees ⋮ Finding approximate repetitions under Hamming distance. ⋮ Relaxed multi-way trees with group updates. ⋮ Space-efficient functional offline-partially-persistent trees with applications to planar point location ⋮ Unnamed Item ⋮ On-line convex planarity testing ⋮ On-line graph algorithms for incremental compilation ⋮ Exponential automatic amortized resource analysis ⋮ Dynamic fractional cascading ⋮ Simplified linear-time Jordan sorting and polygon clipping ⋮ Dynamic maintenance of directed hypergraphs ⋮ Use of dynamic trees in a network simplex algorithm for the maximum flow problem ⋮ A pointer-free data structure for merging heaps and min-max heaps ⋮ Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class ⋮ Lower bounds for planar orthogonal drawings of graphs ⋮ On-line computation of minimal and maximal length paths ⋮ Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits ⋮ Amortized complexity verified ⋮ Maintaining bridge-connected and biconnected components on-line ⋮ SIMPLE: An optimal disk system with two restricted heads ⋮ On the deque conjecture for the splay algorithm ⋮ Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and \(N\)-step SCAN ⋮ A generic arc-consistency algorithm and its specializations ⋮ Sensitivity analysis for Horn formulae ⋮ Complexity of algorithm and operations on trees ⋮ Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying ⋮ AVL trees with relaxed balance ⋮ A generalization of maximal independent sets ⋮ The CB tree: a practical concurrent self-adjusting search tree ⋮ The weighted list update problem and the lazy adversary ⋮ A systematic analysis of splaying ⋮ On sorting, heaps, and minimum spanning trees ⋮ Dynamic algorithms for classes of constraint satisfaction problems ⋮ Partially dynamic maintenance of minimum weight hyperpaths ⋮ Automated Expected Amortised Cost Analysis of Probabilistic Data Structures ⋮ A dynamic location problem for graphs ⋮ The list update problem and the retrieval of sets ⋮ Most uniform path partitioning and its use in image processing ⋮ The derivation of a tighter bound for top-down skew heaps ⋮ Efficient Type-Checking for Amortised Heap-Space Analysis ⋮ A tight amortized bound for path reversal ⋮ On the sequential access theorem and deque conjecture for splay trees ⋮ On-line algorithms for networks of temporal constraints ⋮ Heaps and heapsort on secondary storage ⋮ New results on competitive analysis of online SRPT scheduling ⋮ A PRIORITY QUEUE WITH THE WORKING-SET PROPERTY ⋮ VARIANTS OF (A,B)-TREES WITH RELAXED BALANCE ⋮ Maintaining a topological order under edge insertions ⋮ Semi-dynamic breadth-first search in digraphs ⋮ Incremental convex planarity testing ⋮ Preprocessing of intractable problems ⋮ Manipulating multiple stacks with ordered-heap ⋮ Efficient token-based control in rings. ⋮ The set union problem with dynamic weighted backtracking ⋮ Efficient management of dynamic tables ⋮ Sequential access in splay trees takes linear time ⋮ Two decades of automatic amortized resource analysis ⋮ Type-based analysis of logarithmic amortised complexity ⋮ Maintaining longest paths incrementally ⋮ The amortized complexity of Henriksen's algorithm
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A class of algorithms which require nonlinear time to maintain disjoint sets
- A linear-time algorithm for a special case of disjoint set union
- A new data structure for representing sorted lists
- Updating a balanced search tree in 0(1) rotations
- Organization and maintenance of large ordered indexes
- Symmetric binary B-trees: Data structure and maintenance algorithms
- Gauss codes, planar hamiltonian graphs, and stack-sortable permutations
- Self-adjusting binary search trees
- Worst-case Analysis of Set Union Algorithms
- Design and Analysis of a Data Structure for Representing Sorted Lists
- Efficient Planarity Testing
- Efficiency of a Good But Not Linear Set Union Algorithm
- On self-organizing sequential search heuristics
- Fast Pattern Matching in Strings
- Self-Organizing Binary Search Trees
- Heuristics That Dynamically Organize Data Structures
- Self-Adjusting Heaps
- An improved equivalence algorithm
- Binary Search Trees of Bounded Balance
This page was built for publication: Amortized Computational Complexity