[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:1.9.2.28) 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
--
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
- [igraph] Question on generating connected graphs,
Rossano Gaeta <=