Tight Bounds for On-Line Tree Embeddings

DOI10.1137/S0097539796308710MaRDI QIDQ4268893zbMATH OpenOpenAlexFDO

Authors Sandeep Bhatt, David S. Greenberg, Tom Leighton, Pangfeng Liu

Publication date 28 October 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539796308710

zbMATH Keywords

graph embeddingrandomized algorithm

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• Lower bounds for dynamic tree embedding in bipartite networks
• Load balanced tree embeddings
• On the performance of randomized embedding of reproduction trees in static networks

Cited in

(6)

• Optimal one-page tree embeddings in linear time
• Load balanced tree embeddings
• Lower bounds for dynamic tree embedding in bipartite networks
• Analysis of randomized load distribution for reproduction trees in linear arrays and rings
• The scalability analysis of a parallel tree search algorithm
• Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method

This page was built for publication: Tight Bounds for On-Line Tree Embeddings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4268893)