The Parallel Complexity of Tree Embedding Problems

DOI10.1006/JAGM.1995.1006MaRDI QIDQ4327818zbMATH OpenOpenAlexFDO

Authors Arvind Kumar Gupta, N. Nishimura

Publication date 9 April 1995

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1995.1006

zbMATH Keywords

CREW PRAM algorithmssequential complexitytree embedding problems

Mathematics Subject Classification ID

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

Recommendations

• The parallel complexity of tree embedding problems (extended abstract)
• Parallel Tree Contraction Part 2: Further Applications
• Sequential and parallel algorithms for embedding problems on classes of partial k-trees
• scientific article; zbMATH DE number 3866594
• On the complexity of tree embedding problems

Cited in

(10)

• Embeddings of \(k\)-connected graphs of pathwidth \(k\)
• scientific article; zbMATH DE number 4133492 (Why is no real title available?)
• scientific article; zbMATH DE number 3866594 (Why is no real title available?)
• OPTIMAL PARALLEL ENCODING AND DECODING ALGORITHMS FOR TREES
• Sequential and parallel algorithms for embedding problems on classes of partial k-trees
• The parallel complexity of tree embedding problems (extended abstract)
• Finding smallest supertrees under minor containment
• Notes on the Distributed Computation of Merge Trees on CW-Complexes
• Finding smallest supertrees
• The distributed complexity of locally checkable labeling problems beyond paths and trees

This page was built for publication: The Parallel Complexity of Tree Embedding Problems

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