GSoC 2018: Ideas Page

Introduction

Welcome to Sage's Ideas Page for GSoC 2018!

SageMath's GSoC organization homepage -- the hub for submitting applications and where the everything on Google's side is organized.

Please subscribe to the sage-gsoc mailing list and the GAP developer list for discussion on possible GAP GSoC projects. Also, make sure you have gone through the information regarding application procedures, requirements and general advice. The Application Template is also available on that wiki page. Archives of past GSoC project ideas can be found here.

All projects will start with an introduction phase to learn about Sage’s (or sister projects') internal organization and to get used to their established development process. We also require you to show us that you are able to execute actual development by submitting a relevant patch and/or reviewing a ticket via Trac of the project you are interested in applying to. The developer guide is a great comprehensive resource that can guide you through your first steps in contributing to Sage.

Apart from the project ideas listed below, there is also a comprehensive list of future feature wishes in our trac issue tracker. They might contain the perfect project idea for you we didn't even think about!

Project Ideas

Addition of SPQR-tree to graph module

Mentor

David Coudert

Area

Graph theory

Objective:

The goal of this project is to contribute the graph theory module of SageMath with the addition of the linear time algorithm for partitioning a graph into 3-connected components [1] and the construction of the corresponding SPQR-tree [2]. Then, we will use these algorithms as pre-processing for several graph problems such as Hamiltonian Cycle, TSP, etc.

The preferred approach will be to create an interface for the OGDF library [3] that contains an efficient C++ implementation of the construction of SPQR-trees.

[1] J. E. Hopcroft, R. E. Tarjan: Dividing a Graph into Triconnected Components. SIAM J. Comput. 2(3): 135-158 (1973) [2] C. Gutwenger, P. Mutzel: A Linear Time Implementation of SPQR-Trees. Graph Drawing 2000: 77-90 [3] http://www.ogdf.net/

---

Matroid Theory

Mentor

Stefan van Zwam

Area

Matroid Theory, Graph Theory, Combinatorics

Skills

Strong foundation in (discrete) mathematics (PhD student level), strong programming skills, experience reading research papers

Matroid theory in SageMath can be improved in many ways. Some potential topics, of varying difficulty, are:

---

TEMPLATE

Project Title

Mentor

Name(s)

Area

Mathematical and/or technical scope ...

Skills

What the student should bring ...

...