From Invariants to Canonization in Parallel

DOI10.1007/978-3-540-79709-8_23MaRDI QIDQ3503640zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Graphs of bounded treewidth can be canonized in AC^1
• Canonizing graphs of bounded tree width in logspace
• Canonizing Graphs of Bounded Tree Width in Logspace
• The parallel complexity of graph canonization under abelian group action
• Canonical form for graphs in quasipolynomial time: preliminary report

Cites work

• Embeddings of graphs with no short noncontractible cycles
• Flexibility of polyhedral embeddings of graphs in surfaces
• Graph minors. II. Algorithmic aspects of tree-width
• Graphs on surfaces
• scientific article; zbMATH DE number 5605063 (Why is no real title available?)
• scientific article; zbMATH DE number 4060741 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 1091108 (Why is no real title available?)
• Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus
• Isomorphism testing for embeddable graphs through definability
• On Isomorphism and Canonization of Tournaments and Hypertournaments
• Parallel Tree Contraction Part 2: Further Applications
• Rigidity and separation indices of graphs in surfaces
• Rigidity and separation indices of Paley graphs
• Testing Graph Isomorphism in Parallel by Playing a Game
• The isomorphism problem for classes of graphs closed under contraction

Cited in

(12)

• Towards an isomorphism dichotomy for hereditary graph classes
• Interdefinability of parallel operations in PCF
• Graphs of bounded treewidth can be canonized in AC^1
• Fixed-point definability and polynomial time on chordal graphs and line graphs
• The parallel complexity of graph canonization under abelian group action
• Canonical form for graphs in quasipolynomial time: preliminary report
• Count-free Weisfeiler-Leman and group isomorphism
• The iteration number of colour refinement
• On the parallel complexity of group isomorphism via Weisfeiler-Leman
• Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman
• The isomorphism problem for \(k\)-trees is complete for logspace
• Logarithmic Weisfeiler-Leman identifies all planar graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503640)