|
By identical, I assume you mean isomorphic. See here[^], which speculates that the problem may be NP-intermediate (between P and NP-complete).
Let's call the two graphs G1 and G2. On the surface, the problem seems NP-complete because you have to compare G1 and G2 after renaming the n vertices in G2 using names from G1, so there are n! combinations to try. However, some combinations can be filtered out quickly. For example, a vertex in G2 has to have the same degree (number of edges) as the one it is being compared to in G1. But if this check passes, there's still more checking to do, as in the case of the graph with 6 vertices shown in your link.
|
|
|
|
|
This "same name" talk is confusing. The general problem is that the two graphs have different names for their vertices, so you have to try all possible ways of mapping one graph onto the other. So even if there's there's a vertex A in G1 and a vertex A in G2, that doesn't mean that you don't have to compare A in G1 with B in G2, and so on. You'd only need to compare A to A if you're deliberately being told to test a specific mapping, ignoring all others, or when you're solving the general problem and evaluating each possible mapping in succession.
The neighbours must be the same, not just the degrees. Your example, where all the vertices have the same degree, shows why the problem is difficult. If it's an undirected graph and all the degrees are n-1, then it's easy because both must be complete graphs. If not, then let's say we had a graph with 6 vertices, all of degree 2. How can you tell whether these are two disjoint graphs (two C3's) or a connected bipartite graph? You have to go beyond the vertices' degrees to do that.
On the surface, it looks NP-complete because there are n! possible mappings, and n! is approximated by an exponential function.
|
|
|
|
|
CLOSED
modified 16-Nov-20 11:39am.
|
|
|
|
|
Your first paragraph is correct. So is your second paragraph, but of course all combinations have to be tried before concluding that the graphs are not isomorphic.
Your example shows why the problem is difficult. You have to try all combinations, though optimizations certainly exist. Trivially, the number of vertices in both graphs has to be the same. And if you sort their vertices' degrees, the two sequences have to be the same. But like the 6-vertex graph demonstrated, that isn't enough. There are undoubtedly more optimizations, which is why the article that I linked to speculated that the problem is NP-incomplete (easier than NP-complete). But you'd have to search the net to find the details of those algorithms.
|
|
|
|
|
CLOSED
modified 16-Nov-20 11:39am.
|
|
|
|
|
It appears that I'm more or less answering a homework question, which isn't a good idea for you.
Yes, you have to satisfy the neighbour condition (which will automatically satisfy the degree condition). n is the number of vertices in G2, but G1 must also have n vertices, otherwise the graphs couldn't possibly be isomorphic. There are n! possibilities because you need to try all possible permutations when mapping G2's vertices to G1's. Maybe you get lucky and discover that they're isomorphic when you check the first permutation, or maybe you get unlucky and have to try them all.
|
|
|
|
|
When you are new to this site, any of your posts might be marked as possible spam, in which case it has to be reviewed by one of the admins. It probably happened because your post contained links, and some new members post links that are spam.
This has gone beyond my expertise level. It’s been about 40 years since I last did theoretical computer science. Is the isomorphism problem NP-complete or not? Well, I would trust your second link more, since it’s actually on a theoretical CS site, which carries more weight with me than GeeksForGeeks.
However, it appears that they're talking about two different things. One form of the isomorphism problem allows the graphs to have a different number of vertices. In that case, the goal is to determine whether the larger graph has a subgraph that is an isomorph of the smaller one. This definitely seems NP-complete because you first have to pick one of the C(v1,v2) possible subgraphs before you can even check if it is isomorphic, where v1 and v2 are the number of vertices in G1 and G2 respectively. That’s what the GeeksForGeeks post is talking about, whereas the other one seems to be talking about the simpler version of the problem, where G1 and G2 have the same number of vertices.
So it looks like they're both right. 
|
|
|
|
|
Long Division / Assembly Language Style
I am a little bit embarrassed that I can't figure this out on my own with pencil and paper; in fact, a lot embarrassed
MY QUESTION...
What is the Algorithm for dividing one very large integer by another ?
I don't want to get too ridiculous on my first attempt at this, so I will toss out these sorts of values...
TWO UNSIGNED INTEGERS
- A Thirty-Four Byte Dividend
- A Seventeen Byte Divisor
In bits, that would be
- A 272 Bit Dividend
- And a 136 Bit Divisor
I want to do this using All_Or_Mostly 8-Bit registers to the maximum extent possible.
I am quite surprised that I couldn't find this question answered with a web search.
Can someone tell me what question to ask Google ?
For that matter, is there a better online community than this one for questions such as this one ?
I am totally fine if we start off learning how to do 16-bit division using 8-Bit regs and then move up to 24, 32, 40, 48 etc. dividend sizes
|
|
|
|
|
|
Are you building it on top of an instruction like x86's div, which takes a double-width dividend and a regular-width divisor, and results in a quotient and remainder? Or some other, less convenient, type of division (like MIPS) which divides two equal-sized numbers by each other?
Or is it a from-scratch kind of deal, on a machine without division?
|
|
|
|
|
Have you considered table lookup?
No smiley ... In the days when a CPU filled a rack of boards, and the ALU (Arithmetic/Logic Unit) alone was a least one board, maybe more, there was a machine that did that, although for floating point rather than integer. The most significant bits of the mantissas (always kept normalized, with a hidden MSB) were used as indexes into a huge 2D table in ROM, giving the 11 most significant bits. From that, a Newton iteration was done, doubling the precision for each iteration. The entire iteration was done in hardware: The initial lookup took one clock cycle, each iteration took an extra clock cycle (two for single precision, four for double precision). The final normalization of the result took yet another clock cycle.
This FP divide was so fast that the CPU didn't have any integer divide logic. It was faster to convert the integers to 64 bit FP, do the division and convert back. The FP logic alone was a circuit board about A3 size (i.e. twice the size of a standard typewriter paper) packed with chips.
For all I know, maybe modern CPUs use the same technique today. In the late 1970s, it was so remarkable that the design was presented in internationally recognized professional magazines.
If I were to write a division function for arbitrary length integers (or arbitrary precision float), I would consider seriously something in this direction. If the machine provides a division instruction, you can use that to obtain the first 'n' bits, rather than using a huge lookup table.
|
|
|
|
|
 Interesting history! I'd never heard of this.
|
|
|
|
|
|
Quote: What is the Algorithm for dividing one very large integer by another ?
The first idea that come to mind is the same algorithm that is used by hand, a bunch of subtractions and shifts.
Long subtractions and long shifts are easy in machine language.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
I'm trying to create/solve a puzzle in which you are given tetris-like cages in which digits will be placed but cannot have 2 digits in the same row or same column. The goal is to determine the possibilities of doubles and triples [doubles,triples] for a given cage.
For example, with the cage
[[0,1]
[1,1]]
in which 1's indicate cells in the cage, up to 1 double ([1,0]) is allowed.
The restrictions for the cage input is it has a max width of 8, a max height of 3 and max size (# of 1's) of 8.
Here are some more examples along with there possible outputs:
[[1,1],
[1,0],
[1,0]]
[[1,1],
[1,1]]
[[1,1],
[1,0],
[1,1]]
[[1,1,1],
[1,0,0],
[1,0,0]]
[[1,1,0],
[0,1,1]]
[[1,1,0],
[0,1,0],
[0,1,1]]
[[1,0,0],
[1,1,0],
[1,1,1]]
[[1,1,1],
[1,0,1],
[1,0,1]]
[[1,1,1],
[1,0,1],
[1,1,1]]
Please reach out with any questions. I appreciate the help figuring out how to do this programmatically!
|
|
|
|
|
It's far enough removed from reality that no one seems to care.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
Figured it out. The key was recursion.
|
|
|
|
|
Program-1:
for (i = 0; i < m, i + +){
for (j = 0; j < n, j + +){
if (a = b){
arr[i][j] = 1;
}
else{
arr[i][j] = 2;
}
}
}
for (i = 0; i < m, i + +){
for (j = 0; j < n, j + +){
arr[i] += arr[i][j];
}
}
for (i = 0; i < m, i + +){
if (a = b){
p[i] = i
q [i] = i
}
}
Program-2:
for (i = 0; i < m, i + +){
sum = 0;
for (j = 0; j < n, j + +){
if (a = b){
arr[i][j] = 1
sum += 1;
}
else{
arr[i][j] = 2
}
}
if (c = d){
arr[i] = sum;
p[i] = i
q [i] = i
}
}
I tried to make a time complexity equation.
for program-1:
m*n*c1 + m*n*c2 + m*c3
for program-2
m*n*c1 + m*c2
which one is better and how much? Could you please help on that?
|
|
|
|
|
|
|
You need to account for the "number" of "for loops" also; the total iterations might be equivalent, but not the "setting up and tearing down."
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
I need a routine that will generate a random names for files and folders. As long as they are valid file/folder names it doesn't matter what it is.
I have been thinking up several different ways to do this, but I'm wondering what the community thinks is the best way to do this.
I thought about the Windows API that generates a unique temporary file, but technically that file is unique only within the temp directory.
I thought about generating Guids, but that seems to be frying an egg with a nuclear reactor.
What do you think?
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Richard Andrew x64 wrote: I thought about generating Guids, but that seems to be frying an egg with a nuclear reactor.
What do you think?
I think you are wrong. Using Guids is simple enough and has nothing to do with something like "a nuclear reactor".
|
|
|
|
|
Yes I guess you are right.
Thank you for your response.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
I want to calculate the time complexity and show by the equation for both algorithms. Also, I need a comparison between the two algorithms to show which one is better and why. Could you please help with that? It would be beneficial for me and very much appreciable.
Algorithm-1
--------------------------
1.for 1 to m
for 1 to n
if (some condition)
do something
else
do something
end for
end for
2.for 1 to m
for 1 to n
do something
end for
end for
3.for 1 to m
if (some condition)
do something
end for
4.do something
5.for 1 to m
for 1 to m
if (some condition)
do something
end for
end for
6.for x to y
for 1 to x
if (some condition)
do something
end for
end for
Algorithm-2
--------------------------
1.for 1 to m
for 1 to n
if (condition)
do something
else
do something
end for
if (condition)
do something
end for
2. do something
3.for 1 to m
for 1 to m
if (condition)
do something
for 1 to x
if (condition)
do something
break
end for
if (condition)
do something
end for
end for
Thanks, Advance
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
