zbMATH — the first resource for mathematics

From invariants to canonization in parallel. (English) Zbl 1142.68354
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 216-227 (2008).
Summary: A function \(f\) of a graph is called a complete graph invariant if two given graphs \(G\) and \(H\) are isomorphic exactly when \(f(G) = f(H)\). If additionally, \(f(G)\) is a graph isomorphic to \(G\), then \(f\) is called a canonical form for graphs. Y. Gurevich [“From invariants to canonization”, Bull. EATCS 63, 115–119 (1997; Zbl 0886.68065)] proved that any polynomial-time computable complete invariant can be transformed into a polynomial-time computable canonical form. We extend this equivalence to the polylogarithmic-time model of parallel computation for classes of graphs having either bounded rigidity index or small separators. In particular, our results apply to three representative classes of graphs embeddable into a fixed surface, namely, to 3-connected graphs admitting either a polyhedral or a large-edge-width embedding as well as to all embeddable 5-connected graphs. Another application covers graphs with treewidth bounded by a constant \(k\). Since for the latter class of graphs a complete invariant is computable in NC, it follows that graphs of bounded treewidth have a canonical form (and even a canonical labeling) computable in NC.
For the entire collection see [Zbl 1136.68005].

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX Cite
Full Text: DOI