Parallel Tree Contraction Part 2: Further Applications

DOI10.1137/0220070MaRDI QIDQ3985812zbMATH OpenOpenAlexFDO

Authors Gary L. Miller, J. Reif

Publication date 27 June 1992

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

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

zbMATH Keywords

CRCW PRAMgraph connectivitygraph isomorphismparallel tree contractionsubexpression elimination

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• A simple parallel tree contraction algorithm
• scientific article; zbMATH DE number 4213471
• Parallel algorithms for planar graph isomorphism and related problems
• A Randomized Parallel Algorithm for Planar Graph Isomorphism
• The parallel complexity of tree embedding problems (extended abstract)

Cited in

(29)

• A parallelization of Miller's \(n^{\log n}\) isomorphism technique
• More general parallel tree contraction: Register allocation and broadcasting in a tree
• Planarity testing in parallel
• Completeness results for graph isomorphism.
• An optimal parallel algorithm for planar cycle separators
• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• Bounded contractions of full trees
• Computing the maximal canonical form for trees in polynomial time
• A c^k n 5-approximation algorithm for treewidth
• scientific article; zbMATH DE number 440476 (Why is no real title available?)
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• scientific article; zbMATH DE number 4213471 (Why is no real title available?)
• Approximation of smallest linear tree grammar
• From Invariants to Canonization in Parallel
• The parallel complexity of graph canonization under abelian group action
• A Randomized Parallel Algorithm for Planar Graph Isomorphism
• The Parallel Complexity of Tree Embedding Problems
• scientific article; zbMATH DE number 1973868 (Why is no real title available?)
• A simple parallel tree contraction algorithm
• AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS
• A Faster Implementation of a Parallel Tree Contraction Scheme and Its Application on Distance-Hereditary Graphs
• Sequential random permutation, list contraction and tree contraction are highly parallel
• scientific article; zbMATH DE number 7651141 (Why is no real title available?)
• More general parallel tree contraction: register allocation and broadcasting in a tree
• Randomized parallel list ranking for distributed memory multiprocesors
• Parallel tree-contraction and Fibonacci numbers
• Randomized parallel list ranking for distributed memory multiprocessors.
• The isomorphism problem for \(k\)-trees is complete for logspace
• Subtree isomorphism is in random NC

This page was built for publication: Parallel Tree Contraction Part 2: Further Applications

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