The parallel complexity of tree embedding problems (extended abstract)

DOI10.1007/3-540-55210-3_170zbMath1493.68160OpenAlexW2108744165MaRDI QIDQ5096766

Naomi Nishimura, Arvind Kumar Gupta

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55210-3_170

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)

Related Items

Sequential and parallel algorithms for embedding problems on classes of partial k-trees

Cites Work

• Subtree isomorphism is in random NC
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• Subtree isomorphism is NC reducible to bipartite perfect matching
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XV: Giant steps
• An Efficient Parallel Biconnectivity Algorithm
• Nonconstructive tools for proving polynomial-time decidability
• Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph
• On the Computational Complexity of Combinatorial Problems
• Subtree Isomorphism in O(n5/2)
• The Parallel Evaluation of General Arithmetic Expressions
• Parallelism in random access machines