Hello everybody !!!! I have been willing for some time to implement a recognition algorithm for Interval Graphs [1], and I ended up forgetting to sleep one evening to have it done in the morning. :-)
What I now have is an algorithm which uses PQ-Trees [2] and is able to tell, given a graph, whether it is an interval graph and if so, to enumerate all its possible embeddings. Equivalently, this problem can be seen the following way [3] : Given a binary Matrix, find whether there exists a way to reorder its columns so that each row has all its "ones" on an interval (no "1+0+1+" pattern). It can also, if needed, give all such representations. I could store this code in the graph/ folder, but it would be a pity to do so while it is (slightly) more general. I think it would be better to store it in some place dealing with matrices or binary vectors, but as I do not know these areas I a asking you this very question... Where would you see it fitting ? :-) (As it will probably be a looooong review, even though I did my best to comment the code, please tell me if you would be interested in giving it a look !) Thanks !! Nathann [1] http://en.wikipedia.org/wiki/Interval_graph [2] http://en.wikipedia.org/wiki/PQ_tree [3] http://www.ic.unicamp.br/~meidanis/research/pqr/ -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
