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.

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

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.)

MOCHA (2019)

Understanding and leveraging ‘moments of change’ for pro-environmental behaviour shifts

Read More  

ZARAH (2020)

Women’s labour activism in Eastern Europe and transnationally, from the age of empires to the late 20th century

Read More  

ChaperoneRegulome (2020)

ChaperoneRegulome: Understanding cell-type-specificity of chaperone regulation

Read More