From Invariants to Canonization in Parallel

DOI10.1007/978-3-540-79709-8_23zbMath1142.68354OpenAlexW1777861714MaRDI QIDQ3503640

Oleg Verbitsky, Johannes Köbler

Publication date: 5 June 2008

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79709-8_23

Mathematics Subject Classification ID

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

Related Items (5)

Towards an isomorphism dichotomy for hereditary graph classes ⋮ Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic ⋮ Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$ ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ The isomorphism problem for \(k\)-trees is complete for logspace

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rigidity and separation indices of graphs in surfaces
• Embeddings of graphs with no short noncontractible cycles
• The isomorphism problem for classes of graphs closed under contraction
• Rigidity and separation indices of Paley graphs
• Flexibility of polyhedral embeddings of graphs in surfaces
• Isomorphism testing for embeddable graphs through definability
• Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus
• Testing Graph Isomorphism in Parallel by Playing a Game
• Graph minors. II. Algorithmic aspects of tree-width
• Parallel Tree Contraction Part 2: Further Applications
• On Isomorphism and Canonization of Tournaments and Hypertournaments

This page was built for publication: From Invariants to Canonization in Parallel