Opendata, web and dolomites

SYSTEMATICGRAPH SIGNED

Systematic mapping of the complexity landscape of hard algorithmic graph problems

Total Cost €

0

EC-Contrib. €

0

Partnership

0

Views

0

 SYSTEMATICGRAPH project word cloud

Explore the words cloud of the SYSTEMATICGRAPH project. It provides you a very rough idea of what is the project "SYSTEMATICGRAPH" about.

road    landscapes    networks    mapping    relations    approximability    obtain    deserves    solutions    computationally    similarly    coming    enormously    generality    necessarily    little    sporadic    appear    restricted    investigation    sufficiently    waiting    techniques    search    entire    hard    domain    complexity    dichotomy    full    discovered    setting    usually    levels    communication    systematic    reveal    put    csps    special    classifications    constraint    graph    time    hence    description    methodological    variants    formal    satisfaction    intend    tractable    framework    discovering    successful    survivable    algorithms    unified    computer    parameterized    unification    practical    feasible    classifying    efficient    appearing    comparatively    instead    science    network    context    classic    classification    circuits    patterns    abstract    objects    routing    landscape    relevance    tools    graphs    admit    complete    models    completely    natural    algorithmic    theoretical   

Project "SYSTEMATICGRAPH" data sheet

The following table provides information about the project.

Coordinator
MAX-PLANCK-GESELLSCHAFT ZUR FORDERUNG DER WISSENSCHAFTEN EV 

Organization address
address: HOFGARTENSTRASSE 8
city: MUENCHEN
postcode: 80539
website: n.a.

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˙532˙000 €
 EC max contribution 1˙532˙000 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2016-COG
 Funding Scheme ERC-COG
 Starting year 2017
 Duration (year-month-day) from 2017-07-01   to  2022-06-30

 Partnership

Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    MAX-PLANCK-GESELLSCHAFT ZUR FORDERUNG DER WISSENSCHAFTEN EV DE (MUENCHEN) coordinator 1˙177˙000.00
2    MAGYAR TUDOMANYOS AKADEMIA SZAMITASTECHNIKAI ES AUTOMATIZALASI KUTATOINTEZET HU (BUDAPEST) participant 355˙000.00

Map

 Project objective

Graph-theoretical models are natural tools for the description of road networks, circuits, communication networks, and abstract relations between objects, hence algorithmic graph problems appear in a wide range of computer science applications. As most of these problems are computationally hard in their full generality, research in graph algorithms, approximability, and parameterized complexity usually aims at identifying restricted variants and special cases, which are at the same time sufficiently general to be of practical relevance and sufficiently restricted to admit efficient algorithmic solutions. The goal of the project is to put the search for tractable algorithmic graph problems into a systematic and methodological framework: instead of focusing on specific sporadic problems, we intend to obtain a unified algorithmic understanding by mapping the entire complexity landscape of a particular problem domain.

Completely classifying the complexity of each and every algorithmic problem appearing in a given formal framework would necessarily reveal every possible algorithmic insight relevant to the formal setting, with the potential of discovering novel algorithmic techniques of practical interest. This approach has been enormously successful in the complexity classifications of Constraint Satisfaction Problems (CSPs), but comparatively very little work has been done in the context of graphs. The systematic investigation of hard algorithmic graph problems deserves the same level of attention as the dichotomy program of CSPs, and graph problems have similarly rich complexity landscapes and unification results waiting to be discovered. The project will demonstrate that such a complete classification is feasible for a wide range of graph problems coming from areas such as finding patterns, routing, and survivable network design, and novel algorithmic results and new levels of algorithmic understanding can be achieved even for classic and well-studied problems.

 Publications

year authors and title journal last update
List of publications.
2019 Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, Roman Rabinovich
Routing with congestion in acyclic digraphs
published pages: 105836, ISSN: 0020-0190, DOI: 10.1016/j.ipl.2019.105836
Information Processing Letters 151 2020-04-08
2018 Radu Curticapean
Block interpolation: A framework for tight exponential-time counting complexity
published pages: 265-280, ISSN: 0890-5401, DOI: 10.1016/j.ic.2018.02.008
Information and Computation 261 2020-04-08
2019 Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx
Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms
published pages: 3890-3935, ISSN: 0178-4617, DOI: 10.1007/s00453-019-00579-4
Algorithmica 81/10 2020-04-08
2018 Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, Paweł Rzążewski
Fine-grained complexity of coloring unit disks and balls
published pages: 47-80, ISSN: 1920-180X, DOI: 10.20382/jocg.v9i2a4
Journal of Computational Geometry 9(2) 2020-04-08
2018 Daniel Lokshtanov, Dániel Marx, Saket Saurabh
Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
published pages: 1-30, ISSN: 1549-6325, DOI: 10.1145/3170442
ACM Transactions on Algorithms 14/2 2020-04-08
2018 Daniel Lokshtanov, Dániel Marx, Saket Saurabh
Slightly Superexponential Parameterized Problems
published pages: 675-702, ISSN: 0097-5397, DOI: 10.1137/16m1104834
SIAM Journal on Computing 47/3 2020-04-08
2019 Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen
Subexponential-Time Algorithms for Maximum Independent Set in $$P_t$$ P t -Free and Broom-Free Graphs
published pages: 421-438, ISSN: 0178-4617, DOI: 10.1007/s00453-018-0479-5
Algorithmica 81/2 2020-04-08

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "SYSTEMATICGRAPH" 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 "SYSTEMATICGRAPH" are provided by the European Opendata Portal: CORDIS opendata.

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

PROGRESS (2019)

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

Read More  

DISINTEGRATION (2019)

The Mass Politics of Disintegration

Read More  

VictPart (2019)

Righting Victim Participation in Transitional Justice

Read More