Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with isomorphism-testing
Search options not deleted
user 9025
Algorithmic questions concerning isomorphism testing. A prime example is the graph isomorphism problem, which is to decide if two input graphs are isomorphic. This tag may also be used for isomorphism testing between other objects (such as groups).
2
votes
Accepted
Group acting on two different sets, can isomorphisms be computed efficiently?
I'm still not sure in what form your input is given. I'll assume you have permutations $\lbrace g_1,\ldots,g_k\rbrace$ generating $G$, and permutations $\lbrace h_1,\ldots,h_k\rbrace$ generating $H$, …
- 37.7k
6
votes
Accepted
Why is graph automorphism sometimes easier than canonical labeling (for current software)?
This is not a simple question. One thing to know about the pictures above is that the Miyazaki graphs are hard for nauty because Miyazaki studied how nauty operates and designed the graphs to be as ha …
- 37.7k
3
votes
Accepted
A possible GI isomorphic problem
It is GI-complete. Take two arbitrary connected graphs with degrees at least 2 (obviously a GI-complete class). For each vertex $v$, add a new vertex $v'$ and join it only to $v$. The pairs $\{v,v'\ …
- 37.7k
5
votes
Accepted
Weisfeiler-Lehman test for hypergraphs
You can represent a hypergraph by its vertex-edge incidence graph and apply W-L to that.
- 37.7k
0
votes
Accepted
Canonical form for a bipartite graph
Since you seem to be asking about how to compute it, I'll answer that. With nauty, bliss, Traces, etc, you can specify vertex colours then the canonical form won't mix the colours up. Just use one c …
- 37.7k
6
votes
Accepted
Non-isomorphic walk-regular graphs with the same number of closed walks at any length
You are asking for two non-isomorphic cospectral walk-regular graphs, presumably not vertex-transitive.
The following two are examples. They are bipartite and 4-regular on 18 vertices. Both of them ha …
- 37.7k
5
votes
Number of non-isomorphic block graphs on n nodes
This appears to be http://oeis.org/A035053 . References and formulae are there.
- 37.7k
6
votes
Accepted
Automorphism group of directed complete graph
I'm guessing that by "directed complete graph" you want each edge directed in exactly one of the two possible ways. If so, you have a tournament. Automorphism and isomorphism for tournaments is pote …
- 37.7k
5
votes
Accepted
Linear algebra formulation for colored node graph isomorphism
It is equivalent (up to polynomials). Given a coloured graph $G_1$, add a new node (a colour vertex) for each colour and add edges from it to all vertices with that colour. Next add one more new node …
- 37.7k
9
votes
Selection of an n-vertex graph at random
There is a very efficient method.
See Nicholas C. Wormald Generating Random Unlabelled Graphs
- 37.7k
4
votes
Accepted
Determining graph Isomorphism: combining invariants
There will be strongly-regular graphs of the same parameters with equal values of all those invariants. Since the parameters determine the eigenvalues, all the invariants determined by the spectrum (s …
- 37.7k
1
vote
Isomorphism problem on the class of induced subgraphs of a hypercube
For the "relaxation" to embedding-preserving isomorphisms, note that the $n$-cube has only $2^n n!$ symmetries, so you can try them all in $2^{2n} n!$ time or a little less. That's a lot if only a sm …
- 37.7k
3
votes
Algorithm to determine isomorphism of 2 maximal planar graphs
You didn't say whether your interest is theoretical or practical. If it is theoretical, note that maximal planar graphs can be tested in linear time. See the paper of Hopcroft and Wong mentioned in t …
- 37.7k
4
votes
Accepted
Isomorphism testing in STS(13)
Take the 26-vertex graphs whose vertices are the blocks and where two vertices are joined by an edge if the corresponding blocks have a vertex in common. These two graphs differ in many easily measur …
- 37.7k
4
votes
Relation graph isomorphism to discrete logarithm
This is more of a comment than a new answer because it uses no more technique than Joseph's answer. The expression of the problem in terms of graphs or 0-1 matrices is a red herring and I suggest a mo …
- 37.7k