White Flag !!! Please forget what I said earlier about addition of digraphs... It works fine for graphs, but that's all...
At 3am, it's better for me to sleep than to ask questions... sorry again, and thank you for your answer :-) Nathann On 17 July 2010 01:44, Nathann Cohen <[email protected]> wrote: > :-D > > It's true than when I re-read my question, I am plainly asking "how to > solve an binary program" :-D > > There should be some constraint to add to my question to make it less > powerful than SAT... Sorry for that ^^; > > Nathann > > On 17 July 2010 01:42, Nathann Cohen <[email protected]> wrote: >>> If I am understanding your problem correctly, the decision of the >>> existence of such a set of solutions (doesn't really make sense to >>> have a basis does it? 0,1 vectors in the kernel?) NP-Complete by Karp, >>> The Binary Integer Programming problem. >>> >>> http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems >>> >>> The hardness of this problem is the main difficulty underlying of much >>> of combinatorics. >> >> Hmmmm :-/ >> >> I know I can find a solution through integer programming, but in this >> case I hope to find the whole set of solutions (actually, a basis of >> it) because the problem is very special. I have a DiGraph, and I am >> interested in all the eulerian subdigraphs (a subdigraph is eulerian >> if each vertex as as many incoming edges than outgoing edges). If you >> add two eulerian subgraphs, then forget the edges that were taken two >> times (over Z/2Z), what you get is a new eulerian subdigraph. >> >> "a solution" of my system, is, in this case, any circuit I could find >> for example... >> >> I hoped there was a lazy way to obtain a basis of such a space through >> matrix operations... :-/ >> >> Nathann >> > -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
