Tag: graph-isomorphism

Found 66 results for 'graph-isomorphism'.

1) cc.complexity-theory - Relationship between symmetry and computational intractability?
2) cc.complexity-theory - Can graph isomorphism be decided with square root bounded nondeterminism?
3) graph-theory - Problem of graph bi-partition (related to graph isomorphism)
4) cc.complexity-theory - Isomorphism of ‘ordered’ DAGs / acyclic semiautomata
5) graph-theory - Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?
6) graph-theory - Generating Graphs with Trivial Automorphisms
7) cc.complexity-theory - Complexity of counting graph endomorphisms
8) cc.complexity-theory - What evidence is there that Graph Isomorphism is not in $P$?
9) reference-request - Number of Automorphisms of a graph for graph isomorphism
10) reference-request - Testing isomorphism of asymmetric graphs
11) graph-theory - When replacing an edge with a graph gadget preserves graph isomorphism?
12) graph-theory - automorphism in Cai-Furer-Immerman gadgets
13) graph-theory - Infinitary Counting Logics: 1-sorted vs. 2-sorted framework
14) cc.complexity-theory - Imperfect subgraph isomorphism
15) ds.algorithms - Gentle introduction to graph isomorphism for bounded valance graphs
16) cc.complexity-theory - NP-hardness of a graph partition problem?
17) cc.complexity-theory - Quasi-polynomial time algorithm for permutation group isomorphism
18) cc.complexity-theory - Complexity of simple undirected graph isomorphism problem
19) graph-isomorphism - A Combinatorial algorithm for trivalent graph isomorphism (except some small subclass)
20) graph-isomorphism - Can you find a counter-example for this proposed Graph Isomorphism algorithm?
21) terminology - Graph isomorphism with equivalence relation on the vertex set
22) graph-isomorphism - Is anyone aware of a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm?
23) cc.complexity-theory - GI-hard graph problem not known to be $NP$-complete
24) reductions - Proof of an Ising model representation of graph isomorphism problem
25) cc.complexity-theory - How hard is the Circuit Isomorphism problem?
26) cc.complexity-theory - Evidence that Graph Isomorphism problem is not $NP$-complete
27) graph-theory - Cayley subgraph isomorphism and complexity of linear subcode decision
28) graph-theory - One Generalization of Graph Isomorphism Problem
29) graph-theory - Efficient graph isomorphism for similar graph queries
30) time-complexity - Complexity of unbalanced bipartite isomorphism
31) graph-theory - Complexity of a graph-rewriting problem
32) graph-theory - For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?
33) graph-theory - Does this paper imply graph isomorphism is polynomial for cubic and $4$-regular graphs?
34) reference-request - FPT algorithm for Partial k-tree Isomorphism
35) cc.complexity-theory - Graph Isomorphism Problem
36) cc.complexity-theory - Complexity of finding if a degree bounded graph H is a subgraph of an unbounded graph G
37) cc.complexity-theory - Is DAG isomorphism NP-C
38) graph-isomorphism - Some nuances on Group and Subgroup Isomorphism?
39) cc.complexity-theory - Polynomial Time Algorithm for Graph Isomorphism Testing
40) cc.complexity-theory - What's the status of Babai's Graph isomorphism result?
41) graph-isomorphism - Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?
42) cc.complexity-theory - Complexity of the coset intersection problem
43) cc.complexity-theory - coNP certificate for Graph Isomorphism
44) graph-theory - Number of non-isomorphic connected graphs of $n$ nodes and $m$ edges
45) cc.complexity-theory - How hard is to compute $\Delta_{|V|}$?
46) cc.complexity-theory - On Graph Isomorphism Complete Problems
47) graph-theory - Graph isomorphism problem with invertible adjacency matrices
48) graph-isomorphism - Open problems related to Graph isomorphism
49) graph-theory - Regular Graphs and Isomorphism
50) cc.complexity-theory - What is the current known hardness of Graph Isomorphism?