Amortized Computational Complexity

From MaRDI portal
Revision as of 10:29, 5 February 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Publication:3735083

DOI10.1137/0606031zbMath0599.68046OpenAlexW1987927249WikidataQ56172073 ScholiaQ56172073MaRDI QIDQ3735083

Robert Endre Tarjan

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




Related Items (93)

Efficient dual simplex algorithms for the assignment problemThe list update problem and the retrieval of setsAverage cost of Duval's algorithm for generating Lyndon wordsEfficient algorithms for finding minimum spanning trees in undirected and directed graphsATLAS: automated amortised complexity analysis of self-adjusting data structuresThe pairing heap: A new form of self-adjusting heapSemi-dynamic shortest paths and breadth-first search in digraphsSimple confluently persistent catenable listsLower bounds for monotonic list labelingFast meldable priority queuesSelectively-amortized resource boundingAmortized efficiency of a path retrieval data structureFractional cascading. I: A data structuring techniqueMechanical translation of set theoretic problem specifications into efficient RAM code - a case studyRank-Balanced TreesOn top-down splayingA data structure for arc insertion and regular path findingBatch RSAComplexity and resource bound analysis of imperative programs using difference constraintsType-based cost analysis for lazy functional languagesFinding paths and deleting edges in directed acyclic graphsMaking data structures persistentSplay trees as priority queuesA partially persistent data structure for the set-union problemConnected component and simple polygon intersection searchingTopologically sweeping an arrangementCan Burrows-Wheeler transform be replaced in chain code compression?Worst-case analysis of the set-union problem with extended backtrackingAn on-line graph coloring algorithm with sublinear performance ratioDeletion without rebalancing in multiway search treesSemi-online scheduling: a surveyAmortized Complexity VerifiedRelaxed balance through standard rotationsA study on splay treesFinding approximate repetitions under Hamming distance.Relaxed multi-way trees with group updates.Space-efficient functional offline-partially-persistent trees with applications to planar point locationUnnamed ItemOn-line convex planarity testingOn-line graph algorithms for incremental compilationExponential automatic amortized resource analysisDynamic fractional cascadingSimplified linear-time Jordan sorting and polygon clippingDynamic maintenance of directed hypergraphsUse of dynamic trees in a network simplex algorithm for the maximum flow problemA pointer-free data structure for merging heaps and min-max heapsIncremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn classLower bounds for planar orthogonal drawings of graphsOn-line computation of minimal and maximal length pathsVerifying the correctness and amortized complexity of a union-find implementation in separation logic with time creditsAmortized complexity verifiedMaintaining bridge-connected and biconnected components on-lineSIMPLE: An optimal disk system with two restricted headsOn the deque conjecture for the splay algorithmAmortized analysis of some disk scheduling algorithms: SSTF, SCAN, and \(N\)-step SCANA generic arc-consistency algorithm and its specializationsSensitivity analysis for Horn formulaeComplexity of algorithm and operations on treesChain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splayingAVL trees with relaxed balanceA generalization of maximal independent setsThe CB tree: a practical concurrent self-adjusting search treeThe weighted list update problem and the lazy adversaryA systematic analysis of splayingOn sorting, heaps, and minimum spanning treesDynamic algorithms for classes of constraint satisfaction problemsPartially dynamic maintenance of minimum weight hyperpathsAutomated Expected Amortised Cost Analysis of Probabilistic Data StructuresA dynamic location problem for graphsThe list update problem and the retrieval of setsMost uniform path partitioning and its use in image processingThe derivation of a tighter bound for top-down skew heapsEfficient Type-Checking for Amortised Heap-Space AnalysisA tight amortized bound for path reversalOn the sequential access theorem and deque conjecture for splay treesOn-line algorithms for networks of temporal constraintsHeaps and heapsort on secondary storageNew results on competitive analysis of online SRPT schedulingA PRIORITY QUEUE WITH THE WORKING-SET PROPERTYVARIANTS OF (A,B)-TREES WITH RELAXED BALANCEMaintaining a topological order under edge insertionsSemi-dynamic breadth-first search in digraphsIncremental convex planarity testingPreprocessing of intractable problemsManipulating multiple stacks with ordered-heapEfficient token-based control in rings.The set union problem with dynamic weighted backtrackingEfficient management of dynamic tablesSequential access in splay trees takes linear timeTwo decades of automatic amortized resource analysisType-based analysis of logarithmic amortised complexityMaintaining longest paths incrementallyThe amortized complexity of Henriksen's algorithm




Cites Work




This page was built for publication: Amortized Computational Complexity