scientific article; zbMATH DE number 1088188

zbMATH Open0884.68098MaRDI QIDQ4364501FDOQ4364501

Authors: Samuel R. Buss 

Publication date: 17 November 1997

Title of this publication is not available (Why is that?)

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

zbMATH Keywords

logarithmic time algorithmstree canonization problemtree comparison problem

Mathematics Subject Classification ID

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

Cited In (19)

• Gathering asynchronous and oblivious robots on basic graph topologies under the look-compute-move model
• Title not available (Why is that?)
• A BULT algorithm for tree isomorphism
• Completeness results for graph isomorphism.
• On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
• Optimal gathering of oblivious robots in anonymous graphs
• 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 and its application on trees and rings
• Sorting and ranking of self-delimiting numbers with applications to tree isomorphism
• New invariants for the graph isomorphism problem
• Partially commutative inverse monoids.
• Compressed tree canonization
• Gathering of robots on anonymous grids and trees without multiplicity detection
• A Logspace Algorithm for Partial 2-Tree Canonization
• The parallel complexity of graph canonization under abelian group action
• Equivalence checking for orthocomplemented bisemilattices in log-linear time
• The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics
• The Space Complexity of k-Tree Isomorphism

This page was built for publication:

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