Opendata, web and dolomites

DISTRUCT SIGNED

Structure Theory for Directed Graphs

Total Cost €

0

EC-Contrib. €

0

Partnership

0

Views

0

Project "DISTRUCT" data sheet

The following table provides information about the project.

Coordinator
TECHNISCHE UNIVERSITAT BERLIN 

Organization address
address: STRASSE DES 17 JUNI 135
city: BERLIN
postcode: 10623
website: www.tu-berlin.de

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 Coordinator Country Germany [DE]
 Total cost 1˙826˙773 €
 EC max contribution 1˙826˙773 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2014-CoG
 Funding Scheme ERC-COG
 Starting year 2015
 Duration (year-month-day) from 2015-07-01   to  2020-06-30

 Partnership

Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    TECHNISCHE UNIVERSITAT BERLIN DE (BERLIN) coordinator 1˙826˙773.00

Map

 Project objective

Structural graph theory has proved to be a powerful tool for coping with computational intractability. It provides a wealth of concepts and results that can be used to design efficient algorithms for hard computational problems on specific classes of graphs that occur naturally in applications.

In many applications in computer science, the natural mathematical model are directed graphs. Unfortunately, research in structural graph theory has so far almost exclusively focussed on undirected graphs and no structure theory for directed graphs comparable to the tree-width and graph minors based approach for undirected graphs has been developed that would provide for a similar set of tools and concepts to deal with computational problems on directed graphs.

The objective of this proposal is to develop such a structure theory aimed specifically at algorithmic applications on directed graphs. The novelty of our approach is that

a) it is based on directed minors which allows us to avoid the algorithmic problems faced by existing digraph width measures and has not been studied before in this context and

b) it facilitates our recent proof of the excluded directed grid theorem which is likely to allow entirely new algorithmic techniques for directed graphs.

The focus of the project is on the development of the structural foundations and algorithmic techniques for designing efficient algorithms for a wide range of algorithmic digraph problems. In particular, we will use an approach based on logical definability for developing such algorithmic techniques.

Furthermore, we will apply our methods to two specific application areas, model-checking in computer-aided verification and inference problems in Bayesian networks.

 Publications

year authors and title journal last update
List of publications.
2017 Akhoondian Amiri, Saeed
Structural graph theory meets algorithms: covering and connectivity problems in graphs
published pages: , ISSN: , DOI: 10.14279/depositonce-6538
12 2020-04-15
2017 Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic Van der Zypen, David R. Wood
Majority Colourings of Digraphs
published pages: , ISSN: 1077-8926, DOI: 10.37236/6410
The Electronic Journal of Combinatorics 24/2 2020-04-15
2018 Jaffke, Lars; Kwon, O-joung; Telle, Jan Arne
A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width
published pages: , ISSN: , DOI: 10.4230/lipics.stacs.2018.42
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) 35 2020-04-15
2018 Giannopoulou, Archontia C.; Kwon, O-joung; Raymond, Jean-Florent; Thilikos, Dimitrios M.
A Menger-like property of tree-cut width
published pages: , ISSN: , DOI:
2020-04-15
2016 Amiri, Saeed Akhoondian; Kawarabayashi, Ken-Ichi; Kreutzer, Stephan; Wollan, Paul
The Erdos-Posa Property for Directed Graphs
published pages: , ISSN: , DOI:
2020-04-15
2018 Bonamy, Marthe; Defrain, Oscar; Heinrich, Marc; Raymond, Jean-Florent; Pilipczuk, Michał
Enumerating minimal dominating sets in $K_t$-free graphs and variants
published pages: , ISSN: , DOI:
2020-04-15
2017 Eickmeyer, Kord; Giannopoulou, Archontia C.; Kreutzer, Stephan; Kwon, O-Joung; Pilipczuk, Michal; Rabinovich, Roman; Siebertz, Sebastian
Neighborhood complexity and kernelization for nowhere dense classes of graphs
published pages: , ISSN: , DOI: 10.4230/lipics.icalp.2017.63
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) 44 2020-04-15
2018 Kwon, O-joung; Oum, Sang-il
Scattered classes of graphs
published pages: , ISSN: , DOI:
arXiv.org 2020-04-15
2016 Chatzidimitriou, Dimitris; Giannopoulou, Archontia C.; Maniatis, Spyridon; Requilé, Clément; Thilikos, Dimitrios M.; Zoros, Dimitris
FPT Algorithms for Plane Completion Problems
published pages: , ISSN: , DOI: 10.4230/LIPIcs.MFCS.2016.26
MFCS: Mathematical Foundations of Computer Science 24 2020-04-15
2017 Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos
Packing and covering immersion-expansions of planar sub-cubic graphs
published pages: 154-167, ISSN: 0195-6698, DOI: 10.1016/j.ejc.2017.05.009
European Journal of Combinatorics 65 2020-04-15
2019 Kreutzer, Stephan; de Mendez, Patrice Ossona; Rabinovich, Roman; Siebertz, Sebastian
Algorithmic Properties of Sparse Digraphs
published pages: , ISSN: , DOI: 10.4230/lipics.stacs.2019.46
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) 36 2020-04-15
2018 Gajarský, Jakub; Hliněný, Petr; Lokshtanov, Daniel; Obdržálek, Jan; Ramanujan, M. S.
A New Perspective on FO Model Checking of Dense Graph Classes
published pages: , ISSN: , DOI:
arxiv 2020-04-15
2017 Giannopoulou, Archontia C.; Pilipczuk, Michał; Thilikos, Dimitrios M.; Raymond, Jean-Florent; Wrochna, Marcin
Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
published pages: , ISSN: , DOI: 10.4230/lipics.icalp.2017.57
\"ICALP: International Colloquium on Automata, Languages, and Programming, Jul 2017, Varsovie, Poland. 44th International Colloquium on Automata, Languages, and Programming, 80 (57), pp.1-15, 2017, Leibniz International Proceedings in Informatics (LIPIcs). 〈10.4230/LIPIcs.ICALP.2017.57〉\" 2020-04-15
2019 Hojin Choi, O-joung Kwon, Sang-il Oum, Paul Wollan
Chi-boundedness of graph classes excluding wheel vertex-minors
published pages: 319-348, ISSN: 0095-8956, DOI: 10.1016/j.jctb.2018.08.009
Journal of Combinatorial Theory, Series B 135 2020-04-15
2017 Archontia C. Giannopoulou, Stephan Kreutzer, Sebastian Wiederrecht
Matching Connectivity: On the Structure of Graphs with Perfect Matchings
published pages: 505-511, ISSN: 1571-0653, DOI: 10.1016/j.endm.2017.06.080
Electronic Notes in Discrete Mathematics 61 2020-04-15
2018 Gajarský, Jakub; Kreutzer, Stephan; Nešetřil, Jaroslav; de Mendez, Patrice Ossona; Pilipczuk, Michał; Siebertz, Sebastian; Toruńczyk, Szymon
First-Order Interpretations of Bounded Expansion Classes
published pages: , ISSN: , DOI: 10.4230/lipics.icalp.2018.126
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) 45 2020-04-15
2019 Giannopoulou, Archontia C.; Hatzel, Meike; Wiederrecht, Sebastian
Braces of Perfect Matching Width 2
published pages: , ISSN: , DOI:
2020-04-15
2017 Kim, Eun Jung; Kwon, O-joung
ErdH{o}s-P\'osa property of chordless cycles and its applications
published pages: , ISSN: , DOI:
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms 2020-04-15
2019 Giannopoulou, Archontia; Kwon, O-joung; Raymond, Jean-Florent; Thilikos, Dimitrios M.,
Lean Tree-Cut Decompositions: Obstructions and Algorithms
published pages: , ISSN: , DOI: 10.4230/lipics.stacs.2019.32
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) 36 2020-04-15
2020 Bonamy, Marthe; Defrain, Oscar; Hatzel, Meike; Thiebaut, Jocelyn
Avoidable paths in graphs
published pages: , ISSN: , DOI:
https://hal.archives-ouvertes.fr/hal-02402905 2020-04-15
2018 Bergougnoux, Benjamin; Kwon, O-joung; Kanté, Mamadou Moustapha
An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width
published pages: , ISSN: , DOI:
https://hal.archives-ouvertes.fr/hal-01590820 2020-04-15
2016 Saeed Akhoondian Amiri and Stephan Kreutzer and Roman Rabinovich
DAG-width is PSPACE-complete
published pages: 78--89, ISSN: 0304-3975, DOI: 10.1016/j.tcs.2016.09.011
Theor. Comput. Sci. 655 2019-06-06
2017 Jaffke, Lars; Kwon, O-joung; Telle, Jan Arne
A note on the complexity of Feedback Vertex Set parameterized by mim-width
published pages: , ISSN: , DOI:
5 2019-06-06
2018 Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk
First-Order Interpretations of Bounded Expansion Classes
published pages: , ISSN: , DOI:
ICALP 2018 2019-06-06
2017 Gajarsky, Jakub; Kral, Daniel
Recovering sparse graphs
published pages: , ISSN: , DOI:
7 2019-06-06
2018 Albert Atserias, Stephan Kreutzer, Marc Noy
On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface
published pages: , ISSN: , DOI:
ICALP 2018 2018 2019-06-06
2017 Stephan Kreutzer, Sang-il Oum, Paul D. Seymour, Dominic van der Zypen, David R. Wood
Majority Colourings of Digraphs. Electr. J. Comb. 24(2): P2.25 (2017)
published pages: , ISSN: 1077-8926, DOI:
Electronic Journal of Combinatorics 24(2) 2019-06-06

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "DISTRUCT" project.

For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.

Send me an  email (fabio@fabiodisconzi.com) and I put them in your project's page as son as possible.

Thanks. And then put a link of this page into your project's website.

The information about "DISTRUCT" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.1.)

SuperH (2019)

Discovery and Characterization of Hydrogen-Based High-Temperature Superconductors

Read More  

PROGRESS (2019)

The Enemy of the Good: Towards a Theory of Moral Progress

Read More  

HOLI (2019)

Deep Learning for Holistic Inference

Read More