Revision history [back]

Wow ! Somebody is actually using this code ! Now I'am glad :-)

Well, as said before the minor function translates the code to a LP immediately. I had found a way to write this LP somehow smoothly, just to see how it can be done. I have been lookin for VERY LONG for codes to compute treedecomposition and treewidth (I know that some exists), but people never answered my emails until now. I almost began to write my own, but in any case these alagorithms are REALLY exponential.

As for the graph minor test, honestly, I don't think there exists an implementation anywhere else in the world. I tried this one, and it is slow as hell, but it's more to say "it can be solved through LP" than to solve one exactly.

Of course, as you say, there are ways to improve it by actually looking at the graph (even by just counting edges... God this LP formulation is bad). There are also several equivalent conditions for several graphs (cycles, K_4), but for K_$ it is already a lot of work.

Anyway if you're willing to work on Minors in Sage, count me in. Same goes for treewidth or pathwidth, but I think we should be prepared to deal with some C/C++ code, because anything useful in this context has to be written efficiently.

Oh, that's right, you're not addited to sending patches yet. Well, if you're willing to send this patch about edge counting, we'll have plenty of time to try longer codes afterwards :-)

Nathann

Wow ! Somebody is actually using this code ! Now I'am glad :-)

Well, as said before the minor function translates the code to a LP immediately. I had found a way to write this LP somehow smoothly, just to see how it can be done. I have been lookin for VERY LONG for codes to compute treedecomposition and treewidth (I know that some exists), but people never answered my emails until now. I almost began to write my own, but in any case these alagorithms algorithms are REALLY exponential.

As for the graph minor test, honestly, I don't think there exists an implementation anywhere else in the world. I tried this one, and it is slow as hell, but it's more to say "it can be solved through LP" than to solve one them exactly.

Of course, as you say, there are ways to improve it by actually looking at the graph (even by just counting edges... God this LP formulation is bad). There are also several equivalent conditions for several graphs (cycles, K_4), but for K_$ K_4 it is already a lot of work.

Anyway if you're willing to work on Minors in Sage, count me in. Same goes for treewidth or pathwidth, but I think we should be prepared to deal with some C/C++ code, because anything useful in this context has to be written efficiently.

Oh, that's right, you're not addited to sending patches yet. Well, if you're willing to send this patch about edge counting, we'll have plenty of time to try longer codes afterwards :-)

Nathann