Computer Science – Computational Complexity
Scientific paper
2006-08-18
Computer Science
Computational Complexity
14 pages. A minor correction in the proof of Theorem 4.1 made
Scientific paper
A function $f$ of a graph is called a complete graph invariant if the isomorphism of graphs $G$ and $H$ is equivalent to the equality $f(G)=f(H)$. If, in addition, $f(G)$ is a graph isomorphic to $G$, then $f$ is called a canonical form for graphs. Gurevich proves that graphs have a polynomial-time computable canonical form exactly when they have a polynomial-time computable complete invariant. We extend this equivalence to the polylogarithmic-time model of parallel computation for classes of graphs with bounded rigidity index and for classes of graphs with small separators. In particular, our results apply to three representative classes of graphs embeddable into a fixed surface, namely, to 5-connected graphs, to 3-connected graphs admitting a polyhedral embedding, and 3-connected graphs admitting a large-edge-width embedding. Another application covers graphs with bounded treewidth. Since in the latter case an NC complete-invariant algorithm is known, we conclude that graphs of bounded treewidth have a canonical form (and even a canonical labeling) computable in NC.
Koebler Johannes
Verbitsky Oleg
No associations
LandOfFree
From Invariants to Canonization in Parallel does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with From Invariants to Canonization in Parallel, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and From Invariants to Canonization in Parallel will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-567445