igraph-help
[Top][All Lists]
Advanced

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

[igraph] Why are chordal completions computed by igraph so suboptimal?


From: Szabolcs Horvát
Subject: [igraph] Why are chordal completions computed by igraph so suboptimal?
Date: Tue, 22 Sep 2015 20:27:00 +0200

Dear All,

igraph can compute a fill-in necessary to make a graph chordal.  I noticed that the fill-in it returns is usually far from optimal.  While igraph makes no claims of generating a minimal fill-in, I do wonder if this behaviour is correct or if something is going wrong.

A simple example is a 2D grid graph, where a trivial minimal fill-in is adding the "diagonals" of each "square".

Example in R:

g <- make_lattice(c(2,3))

is_chordal(g, fillin=T)

The fill-in it returns is (6 3) (4 1) (6 1) (5 1). If you plot the graph, you'll see that (6 3) (4 1) is sufficient.  For larger graphs the fill-in tends to be even more suboptimal.

So is this the expected behaviour?

Szabolcs

reply via email to

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