Alogtime algorithms for tree isomorphism, comparison, and canonization

MaRDI QIDQ4364501zbMATH OpenFDO

Authors Samuel R. Buss

Publication date 17 November 1997

zbMATH Keywords

logarithmic time algorithmstree canonization problemtree comparison problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The isomorphism problem for \(k\)-trees is complete for logspace
• Canonizing Graphs of Bounded Tree Width in Logspace
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• Faster Subtree Isomorphism
• A Logspace Algorithm for Partial 2-Tree Canonization

Cited in

(20)

• Completeness results for graph isomorphism.
• On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
• The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics
• New invariants for the graph isomorphism problem
• Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings
• Computing the maximal canonical form for trees in polynomial time
• Inverse monoids: decidability and complexity of algebraic questions.
• Optimal gathering of oblivious robots in anonymous graphs
• Gathering asynchronous and oblivious robots on basic graph topologies under the look-compute-move model
• Compressed tree canonization
• A Logspace Algorithm for Partial 2-Tree Canonization
• The parallel complexity of graph canonization under abelian group action
• scientific article; zbMATH DE number 6970796 (Why is no real title available?)
• The Space Complexity of k-Tree Isomorphism
• A BULT algorithm for tree isomorphism
• Sorting and ranking of self-delimiting numbers with applications to tree isomorphism
• Equivalence checking for orthocomplemented bisemilattices in log-linear time
• Sorting and ranking of self-delimiting numbers with applications to outerplanar graph isomorphism
• Gathering of robots on anonymous grids and trees without multiplicity detection
• Partially commutative inverse monoids.

This page was built for publication: Alogtime algorithms for tree isomorphism, comparison, and canonization

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