The isomorphism problem for $k$-trees is complete for logspace (Q714733): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.ic.2012.04.002
+Normal rank
@@ Property / OpenAlex ID @@
+W2052024655
@@ Property / OpenAlex ID: W2052024655 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4091421
@@ Property / cites work: Q4091421 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of planarity testing
@@ Property / cites work: The complexity of planarity testing / rank @@
+Normal rank
@@ Property / cites work @@
+A very hard log-space counting class
@@ Property / cites work: A very hard log-space counting class / rank @@
+Normal rank
@@ Property / cites work @@
+Linear time algorithms for NP-hard problems restricted to partial k- trees
+Normal rank
@@ Property / cites work @@
+The Space Complexity of k-Tree Isomorphism
@@ Property / cites work: The Space Complexity of k-Tree Isomorphism / rank @@
+Normal rank
@@ Property / cites work @@
+A Logspace Algorithm for Partial 2-Tree Canonization
+Normal rank
@@ Property / cites work @@
+Graph Isomorphism is in SPP
@@ Property / cites work: Graph Isomorphism is in SPP / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
+Normal rank
@@ Property / cites work @@
+Structure and importance of logspace-MOD class
@@ Property / cites work: Structure and importance of logspace-MOD class / rank @@
+Normal rank
@@ Property / cites work @@
+A taxonomy of problems with fast parallel algorithms
+Normal rank
@@ Property / cites work @@
+Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
+Normal rank
@@ Property / cites work @@
+Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.
+Normal rank
@@ Property / cites work @@
+Fast parallel reordering and isomorphism testing of \(k\)-trees
+Normal rank
@@ Property / cites work @@
+Counting quantifiers, successor relations, and logarithmic space
+Normal rank
@@ Property / cites work @@
+Testing Graph Isomorphism in Parallel by Playing a Game
+Normal rank
@@ Property / cites work @@
+Group-theoretic algorithms and graph isomorphism
@@ Property / cites work: Group-theoretic algorithms and graph isomorphism / rank @@
+Normal rank
@@ Property / cites work @@
+Completeness results for graph isomorphism.
@@ Property / cites work: Completeness results for graph isomorphism. / rank @@
+Normal rank
@@ Property / cites work @@
+Isomorphism Testing in Hookup Classes
@@ Property / cites work: Isomorphism Testing in Hookup Classes / rank @@
+Normal rank
@@ Property / cites work @@
+Q4268436
@@ Property / cites work: Q4268436 / rank @@
+Normal rank
@@ Property / cites work @@
+The Isomorphism Problem for k-Trees Is Complete for Logspace
+Normal rank
@@ Property / cites work @@
+Q4273947
@@ Property / cites work: Q4273947 / rank @@
+Normal rank
@@ Property / cites work @@
+From Invariants to Canonization in Parallel
@@ Property / cites work: From Invariants to Canonization in Parallel / rank @@
+Normal rank
@@ Property / cites work @@
+Parallel Tree Contraction Part 2: Further Applications
+Normal rank
@@ Property / cites work @@
+Q4474083
@@ Property / cites work: Q4474083 / rank @@
+Normal rank
@@ Property / cites work @@
+Undirected connectivity in log-space
@@ Property / cites work: Undirected connectivity in log-space / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithmic Aspects of Vertex Elimination on Graphs
+Normal rank
@@ Property / cites work @@
+Graph isomorphism is in the low hierarchy
@@ Property / cites work: Graph isomorphism is in the low hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+On the Hardness of Graph Isomorphism
@@ Property / cites work: On the Hardness of Graph Isomorphism / rank @@
+Normal rank
@@ Property / cites work @@
+Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$
+Normal rank
@@ Property / cites work @@
+Bounded Tree-Width and LOGCFL
@@ Property / cites work: Bounded Tree-Width and LOGCFL / rank @@
+Normal rank
@@ Property / cites work @@
+Isomorphism for graphs of bounded distance width
@@ Property / cites work: Isomorphism for graphs of bounded distance width / rank @@
+Normal rank

The isomorphism problem for \(k\)-trees is complete for logspace (Q714733): Difference between revisions

Latest revision as of 18:54, 5 July 2024

Statements

Sitelinks

Mathematics(1 entry)