Hi, I thought I would take a minute to express my interest in the project mentioned in the title and describe myself a bit before the application procedure. I am a second year PhD student at the University of Waterloo (Waterloo, Ontario, Canada), studying graph algorithms and complexity. I am particularly interested in fixed-parameter analysis of graph problems and fine-grained complexity, though I am also interested in other areas of computer science.
The project looks interesting to me as I am familiar with concepts mentioned in the project description. Modular decompositions, have been used along with the notion of a 'modular-width' of a graph, in order to parameterise several problems and obtain FPT results, as in e.g. [1]. Ideally, I'd also like to see where these notions can be applied to other FPT algorithms as well, but that's probably not the goal of this program. My PhD thesis will likely focus on FPT in some way, and this was one area of literature I was recently reading. Further, for my last MSc (I have two: one in graph algorithms, one in model driven software engineering), I characterised the end-vertices of LexBFS for bipartite permutation graphs (see [2]), so I am familiar with LexBFS quite well too. It looks like the aim of the project is to implement the algorithm for modular decomposition of [3], and that doesn't seem unreasonable, along with adding an efficient representation of LexBFS. Other (stretch) goals listed are split decompositions and skew partitions of graphs. I'm not as familiar with the most recent literature for these concepts: is [4] still the fastest for skew partitions? is [5] best for computing split decompositions? Are there are other ideas that the users/developers of Sage might want that are related? If there are multiple students interested in the same project, as there appears to be, then that might also be of interest. I will try to think of some too. A possible idea (though it's probably 'low-hanging fruit' in the tree of things to do) is to implement other search algorithms in Sage. It looks clear that LexBFS is useful, but does Sage have an implementation of LexDFS [6]? (a quick search in the ticket tracker didn't show anything, but maybe that's because it's done) Lastly, are there any ideas that mentors for this project think might require novel research? That is, developing *new* algorithms (and implementing them) for problems that have not yet been solved. As a PhD student, publications are always worth seeking out, though since that is not the aim of the summer of code, I certainly can't expect it. I have participated in the summer of code program twice before (once with the Java Pathfinder team, and once with a project of TU Vienna, though it is now apart of the AOSSIE), and in the latter case, my algorithms for proof compression lead to two publications (one accepted [7], and one submitted). I suspect such goals might also be of interest to mentors, so I thought I would ask. Over the next few days, I will go through the suggested process of getting familiar with the Sage development process (opening tickets and the like). Until then, any questions and feedback to this post would help in the upcoming application procedure. Thanks, Jan Gorzny [1] https://arxiv.org/abs/1308.2858 [2] http://www.crypticcode.ca/jan.gorzny/wp-content/uploads/2015/09/2015-discrete-lbfs-ends.pdf (to appear in DAM) [3] http://www.cs.toronto.edu/~mtedder/TedderModular.pdf [4] https://link.springer.com/chapter/10.1007%2F978-3-540-89550-3_11 [5] http://epubs.siam.org/doi/10.1137/10080052X [6] http://epubs.siam.org/doi/abs/10.1137/050623498 [7] http://www.crypticcode.ca/jan.gorzny/wp-content/uploads/2015/09/2015-cade-folu.pdf -- You received this message because you are subscribed to the Google Groups "sage-gsoc" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sage-gsoc. For more options, visit https://groups.google.com/d/optout.
