On the public citation graph

The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

https://doi.org/10.1007/bf01762121
0 signed · 113 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-17179-7_28openalex-snapshot
An optimal parallel algorithm for dynamic expression evaluation and its applications
inferredcites →https://doi.org/10.1007/978-1-4684-5511-3_9openalex-snapshot
Optimal Tree Contraction in the EREW Model
inferredcites →https://doi.org/10.1007/bfb0040376openalex-snapshot
Deterministic parallel list ranking
inferredcites →https://doi.org/10.1016/0020-0190(85)90025-0openalex-snapshot
On efficient parallel strong orientation
inferredcites →https://doi.org/10.1016/0890-5401(89)90036-9openalex-snapshot
Faster optimal parallel prefix sums and list ranking
inferredcites →https://doi.org/10.1016/s0019-9958(86)80023-7openalex-snapshot
Deterministic coin tossing with applications to optimal parallel list ranking
inferredcites →https://doi.org/10.1109/sfcs.1985.43openalex-snapshot
Parallel tree contraction and its application
inferredcites →https://doi.org/10.1109/sfcs.1985.9openalex-snapshot
An optimal parallel algorithm for integer sorting
inferredcites →https://doi.org/10.1109/sfcs.1986.10openalex-snapshot
Approximate and exact parallel scheduling with applications to list, tree and graph problems
inferredcites →https://doi.org/10.1137/0214061openalex-snapshot
An Efficient Parallel Biconnectivity Algorithm
inferredcites →https://doi.org/10.1137/0217009openalex-snapshot
Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
inferredcites →https://doi.org/10.1145/12130.12151openalex-snapshot
Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms
inferredcites →https://doi.org/10.1145/2157.322410openalex-snapshot
Applying Parallel Computation Algorithms in the Design of Serial Algorithms
inferredcites →https://doi.org/10.1145/321906.321911openalex-snapshot
On the Parallel Evaluation of Certain Arithmetic Expressions
inferredcites →https://doi.org/10.1145/3318.3478openalex-snapshot
Optimal parallel generation of a computation tree form

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/cpe.700openalex-snapshot
Parallel computation on interval graphs: algorithms and experiments
inferred← citeshttps://doi.org/10.1002/net.20258openalex-snapshot
Collection depots facility location problems in trees
inferred← citeshttps://doi.org/10.1006/jagm.1996.0829openalex-snapshot
Parallel Shortcutting of Rooted Trees
inferred← citeshttps://doi.org/10.1006/jagm.1996.0835openalex-snapshot
A Data Structure for Dynamically Maintaining Rooted Trees
inferred← citeshttps://doi.org/10.1006/jagm.1996.0844openalex-snapshot
Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms
inferred← citeshttps://doi.org/10.1006/jpdc.1994.1067openalex-snapshot
An Optimal Parallel Matching Algorithm for Cographs
inferred← citeshttps://doi.org/10.1007/11561071_26openalex-snapshot
A New Template for Solving p-Median Problems for Trees in Sub-quadratic Time
inferred← citeshttps://doi.org/10.1007/3-540-36265-7_7openalex-snapshot
Evaluating Arithmetic Expressions Using Tree Contraction: A Fast and Scalable Parallel Implementation for Symmetric Multiprocessors (SMPs)
inferred← citeshttps://doi.org/10.1007/3-540-53414-8_43openalex-snapshot
Optimal parallel 3-colouring algorithm for rooted trees and its application
inferred← citeshttps://doi.org/10.1007/3-540-53504-7_97openalex-snapshot
Parallel Breadth-first and Breadth-depth traversals of general trees
inferred← citeshttps://doi.org/10.1007/3-540-54233-7_148openalex-snapshot
Structural parallel algorithmics
inferred← citeshttps://doi.org/10.1007/3-540-56024-6_19openalex-snapshot
Color Set Size problem with applications to string matching
inferred← citeshttps://doi.org/10.1007/3-540-57155-8_266openalex-snapshot
Improved parallel depth-first search in undirected planar graphs
inferred← citeshttps://doi.org/10.1007/3-540-57273-2_48openalex-snapshot
Optimal CREW-PRAM algorithms for direct dominance problems
inferred← citeshttps://doi.org/10.1007/3-540-57785-8_165openalex-snapshot
A simple optimal parallel algorithm for reporting paths in a tree
inferred← citeshttps://doi.org/10.1007/3-540-63307-3_75openalex-snapshot
A centroid labelling technique and its application to path selection in trees
inferred← citeshttps://doi.org/10.1007/978-3-030-51466-2_26openalex-snapshot
Balancing Straight-Line Programs for Strings and Trees
inferred← citeshttps://doi.org/10.1007/978-3-540-24587-2_53openalex-snapshot
Range Mode and Range Median Queries on Lists and Trees
inferred← citeshttps://doi.org/10.1007/978-3-642-40450-4_48openalex-snapshot
Fréchet Queries in Geometric Trees
inferred← citeshttps://doi.org/10.1007/bf01192047openalex-snapshot
An optimal parallel algorithm for planar cycle separators
inferred← citeshttps://doi.org/10.1007/bf01228509openalex-snapshot
Optimal parallel algorithms for multiple updates of minimum spanning trees
inferred← citeshttps://doi.org/10.1007/bf01759076openalex-snapshot
Deterministic parallel list ranking
inferred← citeshttps://doi.org/10.1007/bf01840376openalex-snapshot
Efficient parallel algorithms for graph problems
inferred← citeshttps://doi.org/10.1007/bf01840381openalex-snapshot
Efficient parallel algorithms forr-dominating set andp-center problems on trees
inferred← citeshttps://doi.org/10.1007/bf01944354openalex-snapshot
Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree
inferred← citeshttps://doi.org/10.1007/bfb0040376openalex-snapshot
Deterministic parallel list ranking
inferred← citeshttps://doi.org/10.1007/bfb0040377openalex-snapshot
Optimal parallel algorithms for expression tree evaluation and list ranking
inferred← citeshttps://doi.org/10.1007/bfb0040378openalex-snapshot
Optimal parallel evaluation of tree-structured computations by raking (extended abstract)
inferred← citeshttps://doi.org/10.1007/bfb0057943openalex-snapshot
Parallel computation on interval graphs using PC clusters: Algorithms and experiments
inferred← citeshttps://doi.org/10.1016/0020-0190(90)90196-5openalex-snapshot
A simple randomized parallel algorithm for list-ranking
inferred← citeshttps://doi.org/10.1016/0020-0190(91)90214-3openalex-snapshot
A unified approach to parallel depth-first traversals of general trees
inferred← citeshttps://doi.org/10.1016/0020-0190(92)90045-wopenalex-snapshot
Optimal parallel 3-coloring algorithm for rooted trees and its applications
inferred← citeshttps://doi.org/10.1016/0022-0000(92)90003-2openalex-snapshot
Parallel restructuring and evaluation of expressions
inferred← citeshttps://doi.org/10.1016/0022-0000(93)90042-uopenalex-snapshot
Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
inferred← citeshttps://doi.org/10.1016/0166-218x(90)90083-oopenalex-snapshot
Parallel recognition of complement reducible graphs and cotree construction
inferred← citeshttps://doi.org/10.1016/0196-6774(89)90017-5openalex-snapshot
A simple parallel tree contraction algorithm
inferred← citeshttps://doi.org/10.1016/0304-3975(91)90326-wopenalex-snapshot
On optimal parallel computations for sequences of brackets
inferred← citeshttps://doi.org/10.1016/0743-7315(87)90040-2openalex-snapshot
Randomized parallel speedups for list ranking
inferred← citeshttps://doi.org/10.1016/0890-5401(89)90036-9openalex-snapshot
Faster optimal parallel prefix sums and list ranking
inferred← citeshttps://doi.org/10.1016/0890-5401(91)90019-xopenalex-snapshot
Approximate parallel scheduling. II. Applications to logarithmic-time optimal parallel graph algorithms
inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50022-9openalex-snapshot
Parallel Algorithms for Shared-Memory Machines
inferred← citeshttps://doi.org/10.1016/b978-044482537-7/50005-xopenalex-snapshot
Deterministic Parallel Computational Geometry
inferred← citeshttps://doi.org/10.1016/b978-044482587-2/50152-xopenalex-snapshot
Real-Time Connected Component Labeling on One-Dimensional Array Processors based on Content-Addressable Memory
inferred← citeshttps://doi.org/10.1016/j.comgeo.2015.02.003openalex-snapshot
Fast algorithms for approximate Fréchet matching queries in geometric trees
inferred← citeshttps://doi.org/10.1016/j.ic.2008.04.004openalex-snapshot
Finding the conditional location of a median path on a tree
inferred← citeshttps://doi.org/10.1016/j.ipl.2008.05.023openalex-snapshot
Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees
inferred← citeshttps://doi.org/10.1016/j.ipl.2009.05.005openalex-snapshot
An optimal algorithm for the maximum-density path in a tree
inferred← citeshttps://doi.org/10.1016/j.parco.2006.06.002openalex-snapshot
Parallel skeletons for manipulating general trees
inferred← citeshttps://doi.org/10.1016/j.procs.2011.04.002openalex-snapshot
A Practical Tree Contraction Algorithm for Parallel Skeletons on Trees of Unbounded Degree
inferred← citeshttps://doi.org/10.1016/s0166-218x(99)00221-8openalex-snapshot
Computing Prüfer codes efficiently in parallel
inferred← citeshttps://doi.org/10.1080/00207169308804183openalex-snapshot
Optimal parallel colouring algorithms for totally decomposable graphs
inferred← citeshttps://doi.org/10.1080/10637199408915406openalex-snapshot
THE OPTIMAL LOCATION OF A STRUCTURED FACILITY IN A TREE NETWORK
inferred← citeshttps://doi.org/10.1080/10637199408915409openalex-snapshot
AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS
inferred← citeshttps://doi.org/10.1109/34.159904openalex-snapshot
Parallel architectures and algorithms for image component labeling
inferred← citeshttps://doi.org/10.1109/focs.2019.00073openalex-snapshot
Balancing Straight-Line Programs
inferred← citeshttps://doi.org/10.1109/hicss.1993.284100openalex-snapshot
An efficient EREW algorithm for minimum path cover and Hamiltonicity on cographs
inferred← citeshttps://doi.org/10.1109/hicss.1993.284104openalex-snapshot
The optimal location of a structured facility in a tree network
inferred← citeshttps://doi.org/10.1109/hipc.1997.634483openalex-snapshot
An optimal parallel algorithm for the all-nearest-foreign-neighbors problem in arbitrary dimensions
inferred← citeshttps://doi.org/10.1109/icpads.2002.1183387openalex-snapshot
Efficient parallel algorithms for the r-dominating set and p-center problems on trees
inferred← citeshttps://doi.org/10.1109/ipdps49936.2021.00032openalex-snapshot
Euler Meets GPU: Practical Graph Algorithms with Theoretical Guarantees
inferred← citeshttps://doi.org/10.1109/ipps.1992.223028openalex-snapshot
Optimal algorithms for the vertex updating problem of a minimum spanning tree
inferred← citeshttps://doi.org/10.1109/ipps.1993.262898openalex-snapshot
A parallel algorithm for multiple edge updates of minimum spanning trees
inferred← citeshttps://doi.org/10.1109/ipps.1994.288276openalex-snapshot
Efficient parallel algorithms for tree-related problems using the parentheses matching strategy
inferred← citeshttps://doi.org/10.1109/ispan.1994.367138openalex-snapshot
A parallel algorithm for the single step searching problem
inferred← citeshttps://doi.org/10.1109/sfcs.1991.185429openalex-snapshot
Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees
inferred← citeshttps://doi.org/10.1109/sfcs.1993.366854openalex-snapshot
Optimal parallel all-nearest-neighbors using the well-separated pair decomposition
inferred← citeshttps://doi.org/10.1109/spdp.1991.218186openalex-snapshot
An optimal parallel matching algorithm for cographs
inferred← citeshttps://doi.org/10.1109/spdp.1992.242748openalex-snapshot
A new framework for designing parallel algorithms on series parallel graphs
inferred← citeshttps://doi.org/10.1109/tpds.2004.36openalex-snapshot
Finding r-dominating sets and p-centers of trees in parallel
inferred← citeshttps://doi.org/10.1109/tvlsi.2007.912038openalex-snapshot
Area-Efficient Arithmetic Expression Evaluation Using Deeply Pipelined Floating-Point Cores
inferred← citeshttps://doi.org/10.1137/0222032openalex-snapshot
Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
inferred← citeshttps://doi.org/10.1137/0222033openalex-snapshot
Linear-Processor NC Algorithms for Planar Directed Graphs II: Directed Spanning Trees
inferred← citeshttps://doi.org/10.1137/0404034openalex-snapshot
Optimal Parallel Algorithms for Region Labeling and Medial Axis Transform of Binary Images
inferred← citeshttps://doi.org/10.1137/0406037openalex-snapshot
Efficient Detection and Protection of Information in Cross Tabulated Tables I: Linear Invariant Test
inferred← citeshttps://doi.org/10.1137/s0097539792226825openalex-snapshot
Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
inferred← citeshttps://doi.org/10.1137/s0097539792227077openalex-snapshot
Planar Strong Connectivity Helps in Parallel Depth-First Search
inferred← citeshttps://doi.org/10.1137/s0097539795289859openalex-snapshot
Parallel Algorithms with Optimal Speedup for Bounded Treewidth
inferred← citeshttps://doi.org/10.1137/s0895480191221453openalex-snapshot
Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs
inferred← citeshttps://doi.org/10.1145/100216.100237openalex-snapshot
Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs
inferred← citeshttps://doi.org/10.1145/1148109.1148116openalex-snapshot
Towards automatic parallelization of tree reductions in dynamic programming
inferred← citeshttps://doi.org/10.1145/129712.129762openalex-snapshot
Planar separators and parallel polygon triangulation (preliminary version)
inferred← citeshttps://doi.org/10.1145/142675.142687openalex-snapshot
Optimal parallel algorithms for triangulated simple polygons
inferred← citeshttps://doi.org/10.1145/1480881.1480905openalex-snapshot
The third homomorphism theorem on trees
inferred← citeshttps://doi.org/10.1145/1594834.1480905openalex-snapshot
The third homomorphism theorem on trees
inferred← citeshttps://doi.org/10.1145/1810959.1811002openalex-snapshot
A dynamic data structure for approximate range searching
inferred← citeshttps://doi.org/10.1145/327164.327198openalex-snapshot
Optimal parallel coloring algorithms for a family of tree-representable graphs
inferred← citeshttps://doi.org/10.1145/341800.341818openalex-snapshot
A no-busy-wait balanced tree parallel algorithmic paradigm
inferred← citeshttps://doi.org/10.1146/annurev.cs.03.060188.001313openalex-snapshot
Parallel Algorithmic Techniques For Combinational Computation
inferred← citeshttps://doi.org/10.12694/scpe.v18i1.1231openalex-snapshot
Efficient Implementation of Tree Skeletons on Distributed-Memory Parallel Computers
inferred← citeshttps://doi.org/10.21236/ada200521openalex-snapshot
Parallel Restructuring and Evaluation of Expressions
inferred← citeshttps://doi.org/10.2197/ipsjtrans.7.148openalex-snapshot
Parallel Tree Contraction with Fewer Types of Primitive Contraction Operations and Its Application to Trees of Unbounded Degree
inferred← citeshttps://doi.org/10.22215/etd/2008-08073openalex-snapshot
Algorithms for static and dynamic path problems in trees
inferred← citeshttps://doi.org/10.22215/etd/2014-10404openalex-snapshot
Obstacle-Avoiding Path Existence Queries in a Simple Polygon
inferred← citeshttps://doi.org/10.26634/jele.2.1.1585openalex-snapshot
Area Efficient Architecture And Algorithm For Evaluation Of Arithmetic Expressions
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2022.83openalex-snapshot
Adaptive Massively Parallel Constant-Round Tree Contraction
inferred← citeshttps://doi.org/10.5555/313559.313680openalex-snapshot
A data structure for dynamically maintaining rooted trees
inferred← citeshttps://doi.org/10.5555/313651.313815openalex-snapshot
Fast incremental text editing
inferred← citeshttps://doi.org/10.5860/choice.33-3959openalex-snapshot
Limits to parallel computation: P-completeness theory
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.