Cost Trade-offs in Graph Embeddings, with Applications

DOI10.1145/2157.322401MaRDI QIDQ3763589zbMATH OpenOpenAlexFDO

Authors Jia-Wei Hong, K. Mehlhorn, Arnold L. Rosenberg

Publication date 1983

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL http://edoc.mpg.de/344635

zbMATH Keywords

alternationcost trade-offsdilation-costexpansion- costgeneric graphsgraph embeddingsnondeterminism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the complexity of tree embedding problems
• Embedding complete binary trees into star and Pancake graphs
• On embedding graphs in trees
• Efficient embeddings of ternary trees into hypercubes.
• scientific article; zbMATH DE number 139790

Cited in

(18)

• On embedding graphs in trees
• Optimal dynamic embedding of X-trees into arrays
• On the complexity of tree embedding problems
• On efficient entreeings
• Scheduling task-trees with additive scales on parallel/distributed machines
• Directed virtual path layouts in ATM networks
• Perfect Storage Representations for Families of Data Structures
• Optimal embeddings of butterfly-like graphs in the hypercube
• Minced trees, with applications to fault-tolerant VLSI processor arrays
• A variation on the min cut linear arrangement problem
• scientific article; zbMATH DE number 139790 (Why is no real title available?)
• Recognizing binary Hamming graphs inO(n 2 logn) time
• Salvage-Embeddings of Complete Trees
• Embedding of K_r+K^c_s and K_r+P_s into arbitrary trees
• Scheduling task-tree with additive scales on parallel/distributed machines
• Embeddings on a Boolean cube
• Hypercube embedding heuristics: An evaluation
• A MIMD implementation of a parallel Euler solver for unstructured grids

This page was built for publication: Cost Trade-offs in Graph Embeddings, with Applications

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