Parallel Tree Contraction Part 2: Further Applications
From MaRDI portal
Publication:3985812
DOI10.1137/0220070zbMath0737.68066OpenAlexW2037233409MaRDI QIDQ3985812
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
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Distributed algorithms (68W15)
Related Items
Planarity testing in parallel ⋮ The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ An optimal parallel algorithm for planar cycle separators ⋮ AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS ⋮ Approximation of smallest linear tree grammar ⋮ The parallel complexity of graph canonization under abelian group action ⋮ From Invariants to Canonization in Parallel ⋮ Completeness results for graph isomorphism. ⋮ Unnamed Item ⋮ The isomorphism problem for planar 3-connected graphs is in unambiguous logspace ⋮ Randomized parallel list ranking for distributed memory multiprocessors. ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ More general parallel tree contraction: Register allocation and broadcasting in a tree
