Details

Autor(en) / Beteiligte

• Köbler, Johannes
• Verbitsky, Oleg

Titel

From Invariants to Canonization in Parallel

Ist Teil von

• Computer Science – Theory and Applications, p.216-227

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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. Gurevich [9] proves 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.