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
_______________________________________________ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help