From Invariants to Canonization in Parallel
From MaRDI portal
Publication:3503640
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
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