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

DOI10.1007/3-540-58218-5_16zbMath1502.68228OpenAlexW1515227792MaRDI QIDQ5054759

Arvind Kumar Gupta, Naomi Nishimura

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58218-5_16

Mathematics Subject Classification ID

Trees (05C05) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Sequential and parallel algorithms for embedding problems on classes of partial k-trees ⋮ On maximum common subgraph problems in series-parallel graphs ⋮ Maximum tree-packing in time \(O(n^{5/2})\) ⋮ Maximum tree-packing in time O(n5/2) ⋮ A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs ⋮ Embeddings of \(k\)-connected graphs of pathwidth \(k\) ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• Subtree isomorphism is in random NC
• The subgraph isomorphism problem for outerplanar graphs
• Subtree isomorphism is NC reducible to bipartite perfect matching
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• On simple characterizations of k-trees
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Subtree Isomorphism in O(n5/2)
• The Parallel Evaluation of General Arithmetic Expressions
• Sequential and parallel algorithms for embedding problems on classes of partial k-trees
• The parallel complexity of tree embedding problems (extended abstract)
• A linear time algorithm for finding tree-decompositions of small treewidth

This page was built for publication: Sequential and parallel algorithms for embedding problems on classes of partial k-trees