Click here to Skip to main content
15,508,644 members
Home / Discussions / Algorithms
   

Algorithms

 
QuestionStamp circular trade Pin
Shir Gans29-Nov-20 7:25
Shir Gans29-Nov-20 7:25 
AnswerRe: Stamp circular trade Pin
Gerry Schmitz29-Nov-20 19:40
mveGerry Schmitz29-Nov-20 19:40 
AnswerRe: Stamp circular trade Pin
Mircea Neacsu6-Dec-20 6:45
mvaMircea Neacsu6-Dec-20 6:45 
GeneralRe: Stamp circular trade Pin
Shir Gans6-Dec-20 8:51
Shir Gans6-Dec-20 8:51 
QuestionGiven an array x, get the array y from a data set of arrays which has the smallest distance to x Pin
Member 1499380315-Nov-20 18:17
Member 1499380315-Nov-20 18:17 
QuestionCLOSED Pin
AlgoHelp14-Nov-20 0:31
AlgoHelp14-Nov-20 0:31 
AnswerRe: How to determine if 2 labelled graphs are identical? Pin
Greg Utas14-Nov-20 2:48
mveGreg Utas14-Nov-20 2:48 
GeneralRe: How to determine if 2 labelled graphs are identical? Pin
Greg Utas14-Nov-20 4:04
mveGreg Utas14-Nov-20 4:04 
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.
Robust Services Core | Software Techniques for Lemmings | Articles
The fox knows many things, but the hedgehog knows one big thing.

GeneralCLOSED Pin
AlgoHelp14-Nov-20 4:49
AlgoHelp14-Nov-20 4:49 
GeneralRe: How to determine if 2 labelled graphs are identical? Pin
Greg Utas14-Nov-20 5:03
mveGreg Utas14-Nov-20 5:03 
GeneralCLOSED Pin
AlgoHelp14-Nov-20 5:24
AlgoHelp14-Nov-20 5:24 
GeneralRe: How to determine if 2 labelled graphs are identical? Pin
Greg Utas14-Nov-20 6:41
mveGreg Utas14-Nov-20 6:41 
GeneralRe: How to determine if 2 labelled graphs are identical? Pin
Greg Utas15-Nov-20 2:27
mveGreg Utas15-Nov-20 2:27 
QuestionLong Division / Assembly Language Style Pin
C-P-User-313-Oct-20 5:34
C-P-User-313-Oct-20 5:34 
AnswerRe: Long Division / Assembly Language Style Pin
Richard Deeming13-Oct-20 5:53
mveRichard Deeming13-Oct-20 5:53 
GeneralRe: Long Division / Assembly Language Style Pin
harold aptroot13-Oct-20 6:31
harold aptroot13-Oct-20 6:31 
AnswerRe: Long Division / Assembly Language Style Pin
trønderen13-Oct-20 7:25
trønderen13-Oct-20 7:25 
GeneralRe: Long Division / Assembly Language Style Pin
Greg Utas13-Oct-20 13:04
mveGreg Utas13-Oct-20 13:04 
AnswerRe: Long Division / Assembly Language Style Pin
Gerry Schmitz13-Oct-20 9:33
mveGerry Schmitz13-Oct-20 9:33 
AnswerRe: Long Division / Assembly Language Style Pin
Patrice T6-Nov-20 16:46
mvePatrice T6-Nov-20 16:46 
QuestionFinding possible combinations for tetris-like cages Pin
vinaysingh8424-Sep-20 15:25
vinaysingh8424-Sep-20 15:25 
AnswerRe: Finding possible combinations for tetris-like cages Pin
Gerry Schmitz25-Sep-20 8:41
mveGerry Schmitz25-Sep-20 8:41 
AnswerRe: Finding possible combinations for tetris-like cages Pin
vinaysingh8429-Sep-20 14:15
vinaysingh8429-Sep-20 14:15 
QuestionCalculate time complexity step by step of given two program program Pin
Member 1151248623-Sep-20 1:22
Member 1151248623-Sep-20 1:22 
AnswerRe: Calculate time complexity step by step of given two program program Pin
Richard MacCutchan23-Sep-20 4:34
mveRichard MacCutchan23-Sep-20 4:34 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.