Skip to main content
Computer Science

Return to Question

Notice removed Draw attention by michaeluskov
Bounty Ended with Juho's answer chosen by michaeluskov
Tweeted twitter.com/StackCompSci/status/725153612763115520
Improve statement of problem.
Source Link
D.W. ♦
D.W. ♦
  • 165.5k
  • 21
  • 230
  • 490

Find all non-isomorphic realizations ofgraphs with a particular degree sequence

I have a degree sequence and I want to generate all non-isomorphic realizationsgraphs with that degree sequence, as fast as possible.

The only way I found is generating the first graph using Havel–Hakimithe Havel-Hakimi algorithm and then get othersother graphs by permutating ofpermuting all pairs of edges and trying to use an edge switching operation (( E=E={{v1,v2},{v3,v4}}, E`=E'= {{v1,v3},{v2,v4}}) which; this does not change vertice degree).

Are there any faster and better algorithms?

Find all non-isomorphic realizations of degree sequence

I have a degree sequence and I want to generate all non-isomorphic realizations as fast as possible.

The only way I found is generating first graph using Havel–Hakimi algorithm and then get others by permutating of all pairs of edges and trying to use edge switching operation (( E={{v1,v2},{v3,v4}}, E`= {{v1,v3},{v2,v4}}) which does not change vertice degree).

Are there any faster and better algorithms?

Find all non-isomorphic graphs with a particular degree sequence

I have a degree sequence and I want to generate all non-isomorphic graphs with that degree sequence, as fast as possible.

The only way I found is generating the first graph using the Havel-Hakimi algorithm and then get other graphs by permuting all pairs of edges and trying to use an edge switching operation (E={{v1,v2},{v3,v4}}, E'= {{v1,v3},{v2,v4}}; this does not change vertice degree).

Are there any faster algorithms?

edited title
Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Find all non-isomorphic realizations of graphicaldegree sequence

Notice added Draw attention by michaeluskov
Bounty Started worth 100 reputation by michaeluskov
deleted 3 characters in body
Source Link
michaeluskov
michaeluskov
  • 43
  • 6

I have a graphicaldegree sequence and I want to generate all non-isomorphic realizations as fast as possible.

The only way I found is generating first graph using Havel–Hakimi algorithm and then get others by permutating of all pairs of edges and trying to use edge switching operation (( E={{v1,v2},{v3,v4}}, E`= {{v1,v3},{v2,v4}}) which does not change vertice degree).

IsAre there any faster and better algorithms?

I have a graphical sequence and I want to generate all non-isomorphic realizations as fast as possible.

The only way I found is generating first graph using Havel–Hakimi algorithm and then get others by permutating of all pairs of edges and trying to use edge switching operation (( E={{v1,v2},{v3,v4}}, E`= {{v1,v3},{v2,v4}}) which does not change vertice degree).

Is there any faster and better algorithms?

I have a degree sequence and I want to generate all non-isomorphic realizations as fast as possible.

The only way I found is generating first graph using Havel–Hakimi algorithm and then get others by permutating of all pairs of edges and trying to use edge switching operation (( E={{v1,v2},{v3,v4}}, E`= {{v1,v3},{v2,v4}}) which does not change vertice degree).

Are there any faster and better algorithms?

Source Link
michaeluskov
michaeluskov
  • 43
  • 6