About PROXNET

PROXNET is a project funded by the MSCA program of the European Union. It is hosted at the Department of Informatics of the University of Bergen, within the Algorithms group, with principal researcher Christophe Crespelle and supervised by Pinar Heggernes.

The goal of the PROXNET project is to open a new way for analysing, modelling and managing complex networks, through graph editing problems. The reason why these networks are said to be complex is that they are loosely structured, due to the part of uncertainty and randomness they contain. On the other hand, the real-world context where they come from strongly constrains their organisation and gives them some specific structure. The difficulty in retrieving this structure is that it is altered by the noise resulting from the uncertainty and randomness that these networks contain. In the PROXNET project, we retrieve the hidden structures of complex networks thanks to graph editing problems, which consist in changing some adjacencies of the graph in order to obtain a desired property. We develop the algorithms necessary to solve graph editing problems on huge instances of graphs, we apply them to real-world datasets and use the results obtained in order to design new models of complex networks.

Contact information


e-mail christophe dot crespelle at uib dot no   (dot = ".", at = "@")
Postal address Postboks 7803
5020 Bergen, Norway
Location Høyteknologisenteret
Thormøhlens Gate 55, Bergen

News


01/23/2020 Workshop on Graph Modification: Algorithms, Experiments and New Problems in Bergen, Norway.
12/09/2019 30th International Symposium on Algorithms and Computation – ISAAC 2019 in Shanghai, China.
09/18/2019 Our workshop « Cops and robber: who will win? » is at the Science Week 2019 in Bergen, Norway.
09/18/2019 Our exact solver for Vertex Cover got the 4th prize in the PACE 2019 Challenge.
06/03/2019 Workshop on Kernelization in Bergen, Norway.
03/04/2019 Conference on Algorithms, Optimization and Learning in Dynamics Environments in Hanoi, Vietnam.
11/15/2018 Graph Theory and Applications Workshop in Hanoi, Vietnam.
09/17/2018 Operation Research + Parameterized Complexity Workshop in Solstrand, Norway.
08/09/2018 China-Norway FPT workshop in Bergen, Norway.
03/21/2018 16th Annual Winter School in Algorithms, Graph Theory and Combinatorics in Geilo, Norway.

Software


Coedit Minimal completion, deletion and editing of an arbitrary graph into a cograph.
Released January 2020.
sources

Edgecom Partition of the edges of an undirected graph into communities.
Released January 2020.
sources

CoverEx Exact solver for Vertex Cover in graphs.
Released May 2019.
sources

Publications


[7] Cyclability in Graph Classes.
Christophe Crespelle, Carl Feghali and Petr Golovach.
Submitted journal paper.

[6] Linear-Time Minimal Cograph Editing.
Christophe Crespelle.
Submitted conference paper.

[5] A survey of parameterized algorithms and the complexity of edge modification.
Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin and Petr Golovach.
Submitted journal paper [ arXiv ].

[4] Cyclability in Graph Classes.
Christophe Crespelle, Carl Feghali and Petr Golovach.
In 30th International Symposium on Algorithms and Computation – ISAAC 2019 [ On-line ]. Volume 149 in LIPIcs, pages 16:1-16:13, 2019.

[3] Faster and Enhanced Inclusion-Minimal Cograph Completion.
Christophe Crespelle, Daniel Lokshtanov, Thi Ha Duong Phan and Eric Thierry.
Submitted journal paper [ arXiv ].

[2] On the effectiveness of the incremental approach to minimal chordal edge modification.
Jean Blair and Christophe Crespelle.
Submitted journal paper [ PDF ].

[1] Survey on graph algorithms parameterized by edge edit distances.
Christophe Crespelle.
Preprint [ PDF ].

Acknowledgements


This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 749022. It is also partly funded by the Department of Informatics of the University of Bergen.

[MSCA] [EU] [UiB]