[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[igraph] Question on generating connected graphs

From: Rossano Gaeta
Subject: [igraph] Question on generating connected graphs
Date: Fri, 20 Jul 2012 14:24:46 +0200
User-agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv: Gecko/20120313 Thunderbird/3.1.20

Dear all,

I am starting to use igraph for the following task: the generation of all connected undirected graphs with N nodes. There is a simple algorithm: start with the complete (empty) graph with N vertices and remove (add) one edge at a time, verify connectedness, continue until empty (complete) graph is obtained.

Although this algorithm can work for small N it will not scale for larger values. Can anybody suggest a more clever solution or does igraph include features that could help to speed things up? Furthermore, can anybody point me out to literature dealing with counting the number of such graphs?

Thank you in advance

Rossano Gaeta - Associate Professor

Dipartimento di Informatica
Università di Torino
Corso Svizzera 185, 10149, Torino, Italia

E-mail: address@hidden
Phone : +39 011 67 06 770
Fax   : +39 011 75 16 03

reply via email to

[Prev in Thread] Current Thread [Next in Thread]