Amortized Computational Complexity
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 3770965 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- 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
- An improved equivalence algorithm
- Binary Search Trees of Bounded Balance
- Design and Analysis of a Data Structure for Representing Sorted Lists
- Efficiency of a Good But Not Linear Set Union Algorithm
- Efficient Planarity Testing
- Fast Pattern Matching in Strings
- Gauss codes, planar hamiltonian graphs, and stack-sortable permutations
- Heuristics That Dynamically Organize Data Structures
- On self-organizing sequential search heuristics
- Organization and maintenance of large ordered indexes
- Self-Adjusting Heaps
- Self-Organizing Binary Search Trees
- Self-adjusting binary search trees
- Symmetric binary B-trees: Data structure and maintenance algorithms
- Updating a balanced search tree in 0(1) rotations
- Worst-case Analysis of Set Union Algorithms
Cited in
(only showing first 100 items - show all)- Dynamic algorithms for classes of constraint satisfaction problems
- Mechanical translation of set theoretic problem specifications into efficient RAM code - a case study
- Dynamic maintenance of directed hypergraphs
- Finding paths and deleting edges in directed acyclic graphs
- Rank-Balanced Trees
- A systematic analysis of splaying
- scientific article; zbMATH DE number 7649967 (Why is no real title available?)
- Complexity of algorithm and operations on trees
- Lower bounds for monotonic list labeling
- Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying
- Splay trees as priority queues
- ATLAS: automated amortised complexity analysis of self-adjusting data structures
- Space-efficient functional offline-partially-persistent trees with applications to planar point location
- On top-down splaying
- Relaxed balance through standard rotations
- Relaxed multi-way trees with group updates.
- Semi-dynamic breadth-first search in digraphs
- On sorting, heaps, and minimum spanning trees
- An on-line graph coloring algorithm with sublinear performance ratio
- Partially dynamic maintenance of minimum weight hyperpaths
- Use of dynamic trees in a network simplex algorithm for the maximum flow problem
- Fractional cascading. I: A data structuring technique
- Manipulating multiple stacks with ordered-heap
- Variants of \((a,b)\)-trees with relaxed balance
- Heaps and heapsort on secondary storage
- scientific article; zbMATH DE number 54254 (Why is no real title available?)
- Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and \(N\)-step SCAN
- Maintaining bridge-connected and biconnected components on-line
- Maintaining a topological order under edge insertions
- A tight amortized bound for path reversal
- Finding approximate repetitions under Hamming distance.
- On-line computation of minimal and maximal length paths
- A data structure for arc insertion and regular path finding
- A dynamic location problem for graphs
- Deletion without rebalancing in multiway search trees
- The weighted list update problem and the lazy adversary
- Two decades of automatic amortized resource analysis
- The derivation of a tighter bound for top-down skew heaps
- Batch RSA
- Exponential automatic amortized resource analysis
- A pointer-free data structure for merging heaps and min-max heaps
- Lower bounds for planar orthogonal drawings of graphs
- Efficient dual simplex algorithms for the assignment problem
- Complexity and resource bound analysis of imperative programs using difference constraints
- Type-based cost analysis for lazy functional languages
- Worst-case input generation for concurrent programs under non-monotone resource metrics
- Selectively-amortized resource bounding
- Dynamic fractional cascading
- The CB tree: a practical concurrent self-adjusting search tree
- Most uniform path partitioning and its use in image processing
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Making data structures persistent
- Topologically sweeping an arrangement
- On the deque conjecture for the splay algorithm
- On-line convex planarity testing
- On-line graph algorithms for incremental compilation
- Amortized analysis via coalgebra
- Typable fragments of polynomial automatic amortized resource analysis
- Analysis of smooth heaps and slim heaps
- Can Burrows-Wheeler transform be replaced in chain code compression?
- Efficient management of dynamic tables
- Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class
- Semi-dynamic shortest paths and breadth-first search in digraphs
- From Shapes to Amortized Complexity
- The pairing heap: A new form of self-adjusting heap
- Worst-case analysis of the set-union problem with extended backtracking
- Fast and simple sorting using partial information
- Connected component and simple polygon intersection searching
- Average cost of Duval's algorithm for generating Lyndon words
- Simplified linear-time Jordan sorting and polygon clipping
- Amortized complexity verified
- Efficient token-based control in rings.
- Automated Expected Amortised Cost Analysis of Probabilistic Data Structures
- Amortized efficiency of a path retrieval data structure
- Semi-online scheduling: a survey
- Maintaining longest paths incrementally
- A generic arc-consistency algorithm and its specializations
- A generalization of maximal independent sets
- Preprocessing of intractable problems
- Sensitivity analysis for Horn formulae
- A partially persistent data structure for the set-union problem
- Simple confluently persistent catenable lists
- Efficient Type-Checking for Amortised Heap-Space Analysis
- Incremental convex planarity testing
- New results on competitive analysis of online SRPT scheduling
- On the sequential access theorem and deque conjecture for splay trees
- On-line algorithms for networks of temporal constraints
- The list update problem and the retrieval of sets
- Fast meldable priority queues
- The set union problem with dynamic weighted backtracking
- The list update problem and the retrieval of sets
- AVL trees with relaxed balance
- Sequential access in splay trees takes linear time
- The amortized complexity of Henriksen's algorithm
- Amortized complexity verified
- Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits
- A study on splay trees
- A PRIORITY QUEUE WITH THE WORKING-SET PROPERTY
- Type-based analysis of logarithmic amortised complexity
- SIMPLE: An optimal disk system with two restricted heads
This page was built for publication: Amortized Computational Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3735083)
