Hi, Just a heads up. GSoC is now limited to a maximum of 2 times.
Isuru Fernando On Thu, Mar 9, 2017 at 5:09 AM, Jan Gorzny <[email protected]> wrote: > 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. > -- 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.
