21 September

Quote of the day (Montreal graphs):

To compare the performance of exploration and validation, both algorithms were tested on a variety of random graphs. The first set of parameterized random graphs was generated by starting with a complete 2D lattice (i.e. a grid) and deleting a specified fraction of randomly selected edges such that the graph remains connected. This first family of graphs should be familiar to those who have been forced to drive a car in Montreal (where roads are often under repair in the summer), and are termed Montreal graphs with deletion factor p, or Montreal(p), p ∈ (0,1).

-- from a paper in 1997. I think maybe the term was first used in 1994.

These can also be described as geometric graphs generated by the Erdős-Rényi process,
constrained and to the 4-connected lattice and with a side condition to
maintain connectivity.

I put this first on my Google Plus stream, so I guess this counts as a cross-post.

A montreal graph

with a large number of deletions (large p).

By Gregory Dudek at | Read (1) or Leave a comment |    
Re: Montreal graphs

I just saw this post while trying to find reference for "Montreal Graphs". Thanks, for sharing!

Posted by: Malika Meghjani at February 12,2012 01:51
Please send trackback to:/blog/233/tbping
There are no trackbacks.
Post your own response

Each comment is manually screened for the presence of appropriate and substantive content, due to a constant onslaught of comment-spam. This means there may be a delay before your comment appears.

(Some kind of name is required, will be visible)

Required, whatever you enter will be visible to other users.

(Optional, used for "mailto" link)

Your email address is not required, but if you insert it it will be displayed so people can contact you.

Answer this question correctly to demonstrate that you are not a dumb spambot.

The title for your comment.

Your comment goes here. All relevant comments are welcome, except for those that simply promote an irrelevant product or else are used to fraudulently inflate the link count to an irrelevant web page. They appear after moderation. Don't forget to also fill in the captcha below or your text will be rejected automatically!

You must answer this question to prove you are human
which has the least friendly public image: 1:collie, 2:beagle, 3:doberman, 4:dachsund, 5:dalmatian?

Answer this question correctly to demonstrate that you are not a dumb spambot.